Passwords

Time limit2sMemory limit512 MB

Summary

Count length A to B alphanumeric passwords with mixed case and a digit that avoid blacklist substrings, where digits can stand in for similar letters.

Level: Hard8 of 10
Topics: Dynamic programming, String matching, Trie, Combinatorics
Solved: No attempts yet

Problem

You are back at work and have to pick a new password. The system administrators enforce these rules.

The password uses only letters and digits.
Its length is at least $A$ and at most $B$ .
It contains at least one lowercase letter, one uppercase letter and one digit.
It contains no word from a list of forbidden words (the blacklist).

A blacklist word counts as contained in the password when it appears as a substring, that is, as a consecutive run of characters. Case is ignored in the comparison. For example, swerc is a substring of SwErC, 2016swerc2016 and SWERC2016, but it is not a substring of ICPC or sw16erc.

Digits written in place of letters are caught as well. The digit 0 reads as o, 1 as i, 3 as e, 5 as s and 7 as t. So 5w3rC counts as an occurrence of swerc, and abcL337def contains leet. The digits 2, 4, 6, 8 and 9 read as no letter.

You are given $N$ blacklist words and the two integers $A$ and $B$ . Count the different passwords that obey every rule. The count can be very large, so print it modulo 1000003.

Input

The first line contains two integers $A$ and $B$ , the minimum and the maximum length of the password. The second line contains an integer $N$ , the number of blacklist words. Each of the next $N$ lines contains one blacklist word $W_i$ , written in lowercase letters only.

Output

Print on one line the number of valid passwords modulo 1000003.

Limits

$3 \le A \le B \le 20$
$0 \le N \le 50$
$1 \le |W_i| \le 20$

Examples3

Example 1

Input

3 5
9
swerc
icpc
fbi
cia
bio
z
hi
no
yes

Expected output

Example 2
Input
```
3 3
0
```
Expected output
```
40560
```
Example 3
Input
```
3 3
1
a
```
Expected output
```
37500
```