Problem D
Passwords
It’s that time of the year again when you go back to work and need to choose new passwords for all your services. The rules enforced by the system administrators are very strict, and the password you choose must obey the following restrictions:
-
It must contain only letters and digits.
-
It must have between
and characters (inclusive). -
It must have at least one lowercase letter, one uppercase letter and one digit.
-
It cannot contain any word of a collection of forbidden words (the blacklist).
A word of the blacklist is considered to be contained in the password if it appears as a substring, that is, if it occurs as a consecutive sequence of characters (regardless of it being upper or lower case). For instance, swerc is a substring of SwErC, 2016swerc2016 or SWERC16, but it is not a substring of ICPC or sw16erc.
Additionally, for the purposes of avoiding the blacklist, you cannot use l33t. Specifically, some digits can be interpreted as letters, namely the 0 (’o’), 1 (’i’), 3 (’e’), 5 (’s’) and 7 (’t’). This implies that for example 5w3rC would be an occurrence of swerc, and that abcL337def contains the word leet.
You cannot stop thinking about all these rules and you wonder how many different valid passwords there are... Can you calculate how many passwords would obey these rules?
Task
Given a blacklist with
Input
The first line contains two integers,
Constraints
|
|
|
|
|
Size of the password |
|
|
|
|
|
Number of words in the blacklist |
|
|
|
|
|
Size of each blacklist word |
Output
The output should contain a single line with an integer
indicating the number of valid passwords modulo
Sample Input Explanation
In this case there are exactly
Some examples of valid passwords are: aA1, B23tT, 1g9K or B2j.
Some examples of invalid passwords are: aaA (it does not contain digits), 12a (it does not contain upper case letters),
a12A34 (
Sample Input 1 | Sample Output 1 |
---|---|
3 5 9 swerc icpc fbi cia bio z hi no yes |
607886 |