A positive integer $N$ is called a lucky number if and only if its decimal representation does not contain any element from the set $S$ as a substring. For example, when $S = \{22, 333, 0233\}$, $233$ is a lucky number, while $2333$, $20233$, and $3223$ are not.
Given $N$ and $S$, calculate the number of lucky numbers no greater than $N$.
Input
The first line contains the integer $N$.
The next line contains an integer $M$, representing the number of elements in $S$.
The next $M$ lines each contain a numeric string, representing an element in $S$.
Output
Output a single integer representing the answer modulo $10^9 + 7$.
Constraints
In the table below, $l$ represents the length of $N$, and $L$ represents the sum of the lengths of all strings in $S$.
| Test Case | $l$ | $M$ | $L$ |
|---|---|---|---|
| 1 | $1 \le l \le 6$ | $1 \le M \le 1$ | $1 \le L \le 2$ |
| 2 | $1 \le l \le 8$ | $1 \le M \le 3$ | $1 \le L \le 12$ |
| 3~7 | $1 \le l \le 100$ | $1 \le M \le 50$ | $1 \le L \le 300$ |
| 8~10 | $1 \le l \le 1200$ | $1 \le M \le 100$ | $1 \le L \le 1500$ |
Examples
Input 1
20 3 2 3 14
Output 1
14