30分求助

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 1505
#define P 1000000007
using namespace std;
int nxt[N][10],idx=0,fail[N],m;int ed[N];
char s[N],t[N];
void ins(char *ch){
    int len=strlen(ch+1);
    int now=0;
    rep(i,1,len){
        if(!nxt[now][ch[i]-'0'])nxt[now][ch[i]-'0']=++idx;
        now=nxt[now][ch[i]-'0'];
    }
    ed[now]=1;
}
queue<int>q;
void bfs(){
    rep(i,0,9)if(nxt[0][i])q.push(nxt[0][i]);
    while(!q.empty()){
        int x=q.front();q.pop();
        rep(i,0,9){
            if(!nxt[x][i])nxt[x][i]=nxt[fail[x]][i];
            else fail[nxt[x][i]]=nxt[fail[x]][i],ed[nxt[x][i]]|=ed[nxt[fail[x]][i]];
        }
    }nxt[0][0]=0;
}
int f[N][N][2];
int main(){
    scanf("%s",&s);
    scanf("%d",&m);
    rep(i,1,m){
        scanf("%s",t+1);
        ins(t);
    }
    bfs();
    int n=strlen(s),ans=0;
    f[0][0][0]=1;
    rep(i,0,n-1){
        rep(x,0,idx)if(!ed[x]){
            //cout<<i<<" "<<x<<endl;
            rep(k,0,(s[i]-'0'-1)){
                int to=nxt[x][k];
                if(!ed[to])f[to][i+1][1]=(f[to][i+1][1]+f[x][i][0])%P;
            }
            rep(k,0,9){
                int to=nxt[x][k];
                if(!ed[to])f[to][i+1][1]=(f[to][i+1][1]+f[x][i][1])%P;
            }
            int to=nxt[x][s[i]-'0'];
            if(!ed[to])f[to][i+1][0]=(f[to][i+1][0]+f[x][i][0])%P;
        }
    }
    rep(x,0,idx)if(!ed[x])ans=(ans+f[x][n][1])%P;
    //rep(i,0,n){rep(x,0,idx)printf("%d ",f[x][i][0]);putchar('\n');}
    //putchar('\n');
    //rep(i,0,n){rep(x,0,idx)printf("%d ",f[x][i][1]);putchar('\n');}
    printf("%d\n",(P+ans-1)%P);
    return 0;
}