题目描述

我们称一个正整数 $x$ 是幸运数，当且仅当它的十进制表示中不包含数字串集合 $s$ 中任意一个元素作为其子串。例如当 $s = \{22, 333, 0233\}$ 时，$233$ 是幸运数，$2333$、$20233$、$3223$ 不是幸运数。给定 $n$ 和 $s$，计算不大于 $n$ 的幸运数个数。

答案对 $10^9 + 7$ 取模。

输入格式

第一行有一个整数，表示 $n$。

第二行有一个整数，表示 $s$ 中的元素个数 $m$。

接下来 $m$ 行，每行一个数字串 $s_i$，表示 $s$ 中的一个元素。

输出格式

输出一行一个整数，表示答案对 $10^9 + 7$ 取模的结果。

输入输出样例 #1

输入 #1

20
3
2
3
14

输出 #1

14

说明/提示

样例 1 解释

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

数据规模与约定

对于全部的测试点，保证：

$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$，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。$n$ 没有前导 $0$，但是 $s_i$ 可能有前导 $0$。