HL, HJ and FGD set problem for ZMY everyday. The title of each problem bores them very much. The title is a string which consists only lower case letters. It's length is L, and, of course, the title must contain their names(hl, hj, fgd) as consecutive substrings.More apparently, N evil consecutive substrings should not appear in the title. Any string satisfying the two conditions above is OK.

The task ZMY is to do today is: if they give ZMY 8 problems every week, and the title of each problem should not be repeated, how many (complete) weeks can they set problems?

Input

Multiple test cases.Input terminates by EOF.

For each test case:

The first line contains two space-seperated integers L(0<=L<=10⁹) and N(0<=N<=20). N lines follow, each contains a string (contains only lowercase letters), which is evil.You can assume the total length of the N evil strings is no more than 20.

Output

For each test case output one line contains the answer modudo 1000.

Example

Input:
10 1
zmy
Output:
245