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
hide comments
|
[Rampage] Blue.Mary:
2017-10-23 02:26:27
@Sigma Kappa: your understanding is correct. |
|
Sigma Kappa:
2017-10-23 00:37:33
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? |
|
Eduardo Ribas:
2010-09-27 22:17:39
does the 3 names need to be in order? first hl then hj then fgd? |
| 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 |
RSS