#2524. [SDOI2014] 数数

[SDOI2014] 数数

题目描述

我们称一个正整数 xx 是幸运数,当且仅当它的十进制表示中不包含数字串集合 ss 中任意一个元素作为其子串。例如当 s={22,333,0233}s = \{22, 333, 0233\} 时,233233 是幸运数,23332333202332023332233223 不是幸运数。给定 nnss,计算不大于 nn 的幸运数个数。

答案对 109+710^9 + 7 取模。

输入格式

第一行有一个整数,表示 nn

第二行有一个整数,表示 ss 中的元素个数 mm

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

输出格式

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

20
3
2
3
14
14

提示

样例 1 解释

除了 3,13,2,12,20,143, 13, 2, 12, 20, 14 以外,不大于 2020 的整数都是幸运数字。

数据规模与约定

对于全部的测试点,保证:

1n<1012011 \leq n < 10^{1201}1m1001 \leq m \leq 1001i=1msi15001 \leq \sum_{i = 1}^m |s_i| \leq 1500mini=1msi1\min_{i = 1}^m |s_i| \geq 1,其中 si|s_i| 表示字符串 sis_i 的长度。nn 没有前导 00,但是 sis_i 可能有前导 00