牛数
题号：NC218849
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛的年级主任看到牛牛在英语早读的时候还在想题，就罚牛牛去做数学题，牛牛哪怕数学啊，对于早早看完《高等数学第七版》不知道多少遍的他来说，高中数学的题不知道多简单。
所以牛牛还是开始想OI题了：
现在牛牛的书上有一个不牛的数字串集合 ，假如一个数  的十进制表示中（十进制表示当然没有前导零）， 里的所有元素都不是他的子串，那么这个数  就是牛的。
现在给出一个 ，询问  区间内的牛数的个数。由于答案可能很大，只需要输出答案对 取模后的结果即可。

输入描述:

第一行一个整数 。
第二行一个整数 ，表示  集合的大小。
下面  行每行一个数字串，表示  中的元素。

输出描述:

输出一个整数表示答案。
示例1

输入

复制 
33522
4
122
001
234
123

输出

复制 
32952

备注:

对于前  的数据，有 。
对于另外  的数据，保证。
对于  的数据，有 ，其中 l_i 为第  个数字串的长度，保证数字串为组成。