看到匹配，自然想到AC自动机
控制位数的当然容易做，(emmm) 这里是要求小于(n)，后面不会了怎么办
好像和数位dp有点关系，首先(dp1_{i,j})跑一边，小于(strlen(n))长度的个数
重点来了，(dp2_{i,j,1/0}) 第三维表示是否达到上界
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxn=2000000;
const LL MOD=1e9+7;
LL n,ans,nod,m;
LL son[maxn][20],val[maxn],dp1[6000][6000],dp2[6000][6000][2],fail[maxn];
char book[maxn],s[maxn];
inline void Build(char *s){
LL len=strlen(s),u=0;
for(LL i=0;i<len;++i){
LL c=s[i]-'0';
if(!son[u][c])
son[u][c]=++nod;
u=son[u][c];
}
val[u]|=1;
}
inline void Bfail(){
queue<LL> que;
for(LL i=0;i<10;++i)
if(son[0][i])
que.push(son[0][i]);
while(que.size()){
LL u=que.front(); que.pop();
for(LL i=0;i<10;++i){
LL v=son[u][i];
if(v)
fail[v]=son[fail[u]][i],
val[v]|=val[fail[v]],
que.push(v);
else
son[u][i]=son[fail[u]][i];
}
}
}
inline void Solve(){
dp1[0][0]=1;
for(LL i=0;i<n;++i){
for(LL u=0;u<=nod;++u){
if(val[u])
continue;
for(LL k=0;k<10;++k){
LL v=son[u][k];
if(val[v])
continue;
if(!i&&!k)
continue;
dp1[i+1][v]=(dp1[i+1][v]+dp1[i][u])%MOD;
}
}
}
for(LL i=1;i<n;++i)
for(LL u=0;u<=nod;++u)
ans=(ans+dp1[i][u])%MOD;
dp2[0][0][1]=1;
for(LL i=0;i<n;++i){
for(LL u=0;u<=nod;++u){
if(val[u])
continue;
for(LL k=0;k<10;++k){
LL v=son[u][k];
if(val[v])
continue;
if(!i&&!k)
continue;
dp2[i+1][v][0]=(dp2[i+1][v][0]+dp2[i][u][0])%MOD;
if(book[i]-'0'>k)
dp2[i+1][v][0]=(dp2[i+1][v][0]+dp2[i][u][1])%MOD;
if(book[i]-'0'==k)
dp2[i+1][v][1]=(dp2[i+1][v][1]+dp2[i][u][1])%MOD;
}
}
}
for(LL u=0;u<=nod;++u)
ans=(ans+dp2[n][u][0])%MOD,
ans=(ans+dp2[n][u][1])%MOD;
}
int main(){
scanf(" %s",book);
n=strlen(book);
scanf("%lld",&m);
for(LL i=1;i<=m;++i)
scanf(" %s",s),
Build(s);
Bfail();
Solve();
printf("%lld",ans);
return 0;
}