解题思路

要在超长上界 $n$ 下计数，不能枚举。我们结合Aho–Corasick 自动机和数位 DP（Digit DP）来做：

1. 构建 Aho–Corasick 自动机

1. 插入模式串：将所有 $m$ 个可爱数字串插入字典树，每个结尾节点记录“权重”——该串出现的次数（如果有相同串插入多次，权重大于1）。
2. 构建 fail 指针：BFS 建立 fail 链，并在每个节点汇总其 fail 链上所有模式串的权重，这样在匹配过程中，只要落到某节点，就知道以该位置为结尾的新匹配数。

题目内容

给定 $m$ 个可爱数字串，它们仅由 $0$ ~ $9$ 这九个数字字符构成，且可能包含前导 $0$。

你需要求解，在区间 $[1,n]$ 中，有多少个整数满足，可爱度恰好为 $1$。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。在这里，一个整数的可爱度定义为：

• 取出一段连续的数位，如果这段数位恰好是给定的 $m$ 个可爱数字串中的一个或多个(完全匹配)，则可爱度加上这个匹配的次数；

• 对于同一段连续的数位，仅计算一次可爱度。

举例说明，如果有两个可爱串，分别是 $1110$ 和 $111$，那么 $21110$ 可爱度不为 $1$，因为它同时包含了两个可爱串；$1111$ 的可爱度为 $2$，因为包含了两次 $111$。

输入描述

第一行输入两个整数 $n,m(1\leq n\leq 10^{1000};1\leq m\leq 1000)$，表示询问区间的范围、给定的可爱数字串的数量。

接下来的 $m$ 行，每行输入一个长度不超过 $10^3$、仅由 $0$ ~ $9$ 这十个数字字符构成的数字串 $s$，代表一个可爱数字串。可能包含前导 $0$。

除此之外，保证单个测试文件给出的 $s$ 的字符数量之和不超过 $10^3$。

输出描述

输出一个整数，表示在区间 $[1,n]$ 中可爱度恰好为 $1$ 的数字个数。由于答案可能很大，请输出答案对 $10^9 +7$ 取模后的结果。

示例1

输入

2000 2
1110
111

输出

9

说明

在区间 $[1,2000]$ 中，可爱度恰好为 $1$ 的数字有 $111,1112,1113,1114,1115,1116,1117,1118,1119$，一共 $9$ 个。

示例2

输入

1120 2
111
111

输出

0