题目描述

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

给定 $n$ 和 $S$，计算不大于 $n$ 的幸运数个数。

输入格式

输入的第一行包含整数 $n$。

接下来一行一个整数 $m$，表示 $S$ 中元素的数量。

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

输出格式

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

20
3
2
3
14

14

提示

$1 \le n \le 10^{1200}$，$1 \le m \le 100$，$1 \le \sum_{i=1}^{n} |S_i| \le 1500$，$n$ 没有前导 $0$，$S_i$ 可能有前导 $0$。