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

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

参考：

绝对（对我来说）是道难题，尤其是很久不写AC自动机与数位dp的我……

首先n特别大，必须得考虑数位dp。

其次给了一堆串，要求不能出现这些串，先建AC自动机再说。

于是得出了一个愉快的结论：在AC自动机上跑数位dp（写到这里我只想用CaO来表达我的心情）

设$f[i][j][0/1]$为填到$i$数位，当前在AC自动机的$j$节点处，已经小于等于/大于到$i$位的原数。

此时需要注意：为了方便（因为参考是这么写的233），我们正着扫n而非以前的套路倒着扫n，这样做会带来一些问题，于是我们将小于等于也拆开，分别用0和1表示。

（PS：那么反着扫不知道是否可行……以及如果要反着扫的话可能需要反着存串。）

dp式子就不细讲了，直接看代码理解吧。唯一要注意的是不能有前导0所以第一层我们要特殊处理。

#include

q; tr[0].fail=0; for(int i=0;i<10;i++){ int u=tr[0].a[i]; if(u){ tr[u].fail=0;q.push(u); } } while(!q.empty()){ int u=q.front();q.pop(); for(int i=0;i<10;i++){ if(tr[u].a[i]){ int v=tr[u].a[i]; tr[v].fail=tr[tr[u].fail].a[i]; tr[v].ed|=tr[tr[tr[u].fail].a[i]].ed; q.push(v); }else tr[u].a[i]=tr[tr[u].fail].a[i]; } }}inline int add(int x,int y){ x+=y;if(x>=p)x-=p;return x;}int main(){ int n,m; scanf("%s%d",s0,&m); while(m--){ scanf("%s",s);insert(); } getfail(); n=strlen(s0); int ans=0; for(int i=1;i<10;i++){ int v=tr[0].a[i],w=s0[0]-'0'; if(!tr[v].ed){ if(i