GEN2 - Text Generater II

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. Its 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-separated integers L (0<=L<=109) 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 modulo 1000.

Example

Input:
10 1
zmy

Output:
245

Added by:Fudan University Problem Setters
Date:2007-09-20
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO
Resource:description by Blue Mary; standard program and test data by g201513

hide comments
2017-10-23 02:26:27 [Rampage] Blue.Mary
@Sigma Kappa: your understanding is correct.
2017-10-23 00:37:33 Sigma Kappa
I have the same question. "Consecutive substring" means just plain regular substring? So, the question asks, essentially, about the number of strings of length L such that none of the given N strings appear in it as a substring, and all of the three strings do appear. Right?...
2012-07-09 15:00:07 梅塔特隆
Is "consecutive" means the three words must be followed one by one?
2010-09-27 22:17:39 Eduardo Ribas
does the 3 names need to be in order? first hl then hj then fgd?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.