Description

We call a positive integer $x$ 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$, compute the number of lucky numbers not greater than $n$.

The answer is taken modulo $10^9 + 7$.

Input Format

The first line contains an integer $n$.

The second line contains an integer $m$, the number of elements in $s$.

The next $m$ lines each contain a digit string $s_i$, representing an element of $s$.

Output Format

Output a single line containing one integer, the answer modulo $10^9 + 7$.

20
3
2
3
14

14

Hint

Sample 1 Explanation

Except for $3, 13, 2, 12, 20, 14$, all integers not exceeding $20$ are lucky numbers.

Constraints

For all testdata, it is guaranteed that:

$1 \leq n < 10^{1201}$, $1 \leq m \leq 100$, $1 \leq \sum_{i = 1}^m |s_i| \leq 1500$, $\min_{i = 1}^m |s_i| \geq 1$, where $|s_i|$ denotes the length of string $s_i$. $n$ has no leading $0$, but $s_i$ may have leading $0$.

Translated by ChatGPT 5