[Sdoi2014]数数

时间限制:10s      空间限制:512MB

题目描述

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


输入格式


    输入的第一行包含整数N。
    接下来一行一个整数M,表示S中元素的数量。
    接下来M行,每行一个数字串,表示S中的一个元素。


输出格式

    输出一行一个整数,表示答案模109+7的值。


样例输入

    20
    3
    2
    3
    14

样例输出

    14

提示

 下表中l表示N的长度,L表示S中所有串长度之和。

1 < =l < =1200 , 1 < =M < =100 ,1 < =L < =1500


题目来源

Round 1 day 1