题目内容

在一个安全审计系统中，每个正整数都会被转换为其十进制表示（不含前导零）。系统预先录入了一些由数字字符构成的‘危险片段’。对于一个给定的正整数，我们定义它的‘风险值’为：扫描其十进制表示的所有连续子串，若某个子串与某个危险片段完全相同，则增加该危险片段对应的权重（如果有多个相同的危险片段，则权重累加）；但同一个子串不管匹配到多少个危险片段，最多只计算一次该子串对应的全部权重。换句话说，风险值等于所有位置结尾的匹配权重之和，其中每个位置结尾的匹配权重就是所有在此处结束的危险片段的出现次数之和（同一位置只累加一次）。

现在，给定正整数 $N$ 和 $m$ 个危险片段，请你求出在区间 $[1,N]$ 中，风险值恰好为 $1$ 的整数有多少个。由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

约束：$N$ 的十进制长度不超过 1000，$m \le 1000$，每个危险片段的长度不超过 1000，且所有危险片段的长度之和不超过 1000。

输入描述

第一行包含一个由数字字符组成的字符串 $N$ 和一个整数 $m$，分别表示上限值和危险片段的个数。接下来的 $m$ 行，每行包含一个仅由数字字符 0 到 9 组成的字符串，表示一个危险片段。