感觉我太不自信了，其实思路都是对的，就是不敢写，想到了也不写。
这题综合了一些东西。
首先非常套路对于所有模式串建AC自动机，维护出 (Trie) 图上哪些点不能到达
如何限制 (le n) ？这就很像数位dp了，dp状态多一维 (0/1) 表示是否顶到上界
我开心地写完了这个dp却发现WA40
到讨论区发现被下面那组hack了
2000
1
001
很明显是前导零的问题，但是我怀疑是别的问题懒得改。最后就是这个问题。
如果还有前导零那么当前点设为 (0) ，否则走 (Trie) 图上的出边。
干脆换成记搜写数位dp了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define x first
#define y second
#define sz(v) (int)v.size()
#define pb(x) push_back(x)
#define mkp(x,y) make_pair(x,y)
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=0;c=getchar();}
while(isdigit(c))x=x*10+c-'0',c=getchar();
return f?x:-x;
}
#define mod 1000000007
#define N 1505
char n[N];
int m,Len,ch[N][10],tot,dp[N][N][2][2],fail[N];
bool en[N];
void fmod(int&x){x-=mod,x+=x>>31&mod;}
void insert(char*str){
int u=0,len=strlen(str);
for(int i=0;i<len;++i){
int c=str[i]-'0';
if(!ch[u][c])ch[u][c]=++tot;
u=ch[u][c];
}
en[u]=1;
}
void build_fail(){
queue<int>q;
for(int i=0;i<10;++i)if(ch[0][i])q.push(ch[0][i]);
while(!q.empty()){
int u=q.front();q.pop();
en[u]|=en[fail[u]];
for(int i=0;i<10;++i)
if(ch[u][i])fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
else ch[u][i]=ch[fail[u]][i];
}
}
int dfs(int u,int pos,int limit,int lead){
if(!pos)return !en[u];
if(en[u])return 0;
if(~dp[u][pos][limit][lead])return dp[u][pos][limit][lead];
int up=limit?n[pos-1]-'0':9,res=0;
for(int i=0;i<=up;++i)fmod(res+=dfs(lead&&!i?0:ch[u][i],pos-1,limit&&i==up,lead&&!i));
return dp[u][pos][limit][lead]=res;
}
signed main(){
scanf("%s%d",n,&m),Len=strlen(n);
for(int i=1;i<=m;++i){
static char str[N];
scanf("%s",str),insert(str);
}
build_fail();
reverse(n,n+Len);
memset(dp,-1,sizeof(dp));
printf("%d
",(dfs(0,Len,1,1)+mod-1)%mod);
return 0;
}