P3311 [SDOI2014] Counting

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$.

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 a single line containing one integer, the answer modulo $10^9 + 7$.

#### 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