题目描述

HL、HJ 和 FGD 每天都给 ZMY 出题，题目的标题一直困扰着他们。

标题是由小写的英文字母组成的，并且长度为指定的 $L$，同时还要满足两个条件：

1. 标题必须包含 HL、HJ、FGD 三个人的名字的小写字母
2. 同时不能够包含 $N$ 个给定的字符串。

假设三位大佬每周给 ZMY 出 $8$ 道题（在这个世界每周有 $7$ 天），同时还要保证题目的标题互不相同，请问大佬们的题目最多能出多少周？（只计算完整的 $7$ 天，如果有多出来的几天不算一周）。

输入格式

多组输入，遇到EOF停止。

$N$ 为给定的不能包含的字符串数量。

后面 $N$ 行，每行一个字符串。

输出格式

输出一行，表示周数，答案模除 $1000$。

10 1
zmy

245

数据范围

$0 \le L \le 10^9$ 且 $0\le N\le 20$。

每个禁用字符串的长度不超过 $20$。每组输入中，所有禁用字符串的长度之和不超过 $20$。