bzoj#P3530. [Sdoi2014] 数数

[Sdoi2014] 数数

题目描述

我们称一个正整数 nn 是幸运数,当且仅当它的十进制表示中不包含数字串集合 SS 中任意一个元素作为其子串。例如当 S={22, 333, 0233}S=\{22,~333,~0233\} 时,233233 是幸运数,2333, 20233, 32232333,~20233,~3223 不是幸运数。

给定 nnSS,计算不大于 nn 的幸运数个数。

输入格式

输入的第一行包含整数 nn

接下来一行一个整数 mm,表示 SS 中元素的数量。

接下来 mm 行,每行一个数字串,表示 SS 中的一个元素。

输出格式

输出一行一个整数,表示答案模 109+710^9+7 的值。

20
3
2
3
14
14

提示

1n1012001 \le n \le 10^{1200}1m1001 \le m \le 1001i=1nSi15001 \le \sum_{i=1}^{n} |S_i| \le 1500nn 没有前导 00SiS_i 可能有前导 00