مسائلة قحبة3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
#define ld long double
#define int long long
#define F first
#define S second
#define Lnode 2*node+1
#define Rnode 2*node+2
#define MID (l+r>>1)
#define el '\n'
#define coutf(x) for(auto v:(x)) cout<<v<<' '; cout<<el
#define coutp(x) for(auto v:(x)) cout<<v.F<<' '<<v.S<<el
#define cinl(x) for(auto &v:(x)) cin>>v;
#define all(x)  x.begin(),x.end()
#define ll long long
#define sz(x)  (int)x.size()
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define vi vector<ll>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
const int N=5005,mod=1e9+7;
using ull = unsigned long long;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
struct aho_corasick {
    struct trie_node {
        vector<int> pIdxs; //probably take memory limit
        map<char, int> next;
        int fail;
        trie_node() :  fail(0) {}
        bool have_next(char ch) {
            return next.find(ch) != next.end();
        }
        int& operator[](char ch) {
            return next[ch];
        }
    };
    vector<trie_node> t;
    vector<string> patterns;
    vector<int> end_of_pattern;
    vector<bool>found;

    vector<vector<int>> adj;
    int insert(const string &s, int patternIdx) {
        int root = 0;
        for (const char &ch : s) {
            if (!t[root].have_next(ch)) {
                t.push_back(trie_node());
                t[root][ch] = t.size() - 1;
            }
            root = t[root][ch];
        }
        t[root].pIdxs.push_back(patternIdx);
        return root;
    }
    int next_state(int cur, char ch) {
        while (cur > 0 && !t[cur].have_next(ch))
            cur = t[cur].fail;
        if (t[cur].have_next(ch))
            return t[cur][ch];
        return 0;
    }
    void buildAhoTree() {
        queue<int> q;
        for (auto &child : t[0].next)
            q.push(child.second);

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (auto &child : t[cur].next) {
                int k = next_state(t[cur].fail, child.first);
                t[child.second].fail = k;
                vector<int> &idxs = t[child.second].pIdxs;
                //dp[child.second] = max(dp[child.second],dp[k]);
                idxs.insert(idxs.end(), all(t[k].pIdxs));
                q.push(child.second);
            }
        }
    }


    void buildFailureTree() {
        adj = vector<vector<int>>(t.size());
        for (int i = 1; i < t.size(); i++)
            adj[t[i].fail].push_back(i);
    }
    aho_corasick(const vector<string> &_patterns) {
        t.push_back(trie_node());
        patterns = _patterns;
        end_of_pattern = vector<int>(patterns.size());
        found=vector<bool>(patterns.size(),false);
        for (int i = 0; i < patterns.size(); i++)
            end_of_pattern[i] = insert(patterns[i], i);
        buildAhoTree();
        //buildFailureTree();
    }
    vector<bool> match(const string &str) {
        int k = 0;
        int sum=0;

        vector<vector<int>> rt(patterns.size());
        for (int i = 0; i < str.size(); i++) {
            k = next_state(k, str[i]);
            for (auto &it : t[k].pIdxs)
                found[it]=1;
        }
       return found;
    }
};
ll n,k;
ll dp[55][1005][2][2];
string s1,s2;
string s;
vector<ll>num;
ll digit(ll i,ll node,bool found,bool f,aho_corasick &ac)
{
    if (i==n)return (found>0);
    ll &ret=dp[i][node][found][f];
    if (~ret)return ret;
    ll res=0;
    int LMT;
    if (f==0)LMT=num[i];
    else LMT=9;
    for (int dgt=0;dgt<=LMT;dgt++)
    {
        int nf=f;
        if (f==0&&dgt<LMT)nf=1;
        char ch=char('0'+dgt);
        int nnode=ac.next_state(node,ch);
        bool nfound =found;
        if (!ac.t[nnode].pIdxs.empty())nfound=1;
            res+=digit(i+1,nnode,nfound,nf,ac);
        if (res>=mod)res-=mod;
    }
    return ret=res;
}
ll fun(string s,aho_corasick &ac){
    num.clear();
    for (auto it:s)
    {
        num.push_back(it-'0');
    }

    n=s.size();

    memset(dp,-1,sizeof dp);
    ll ans=digit(0,0,0,0,ac);
    return ans;
}
string minus1(string s)
{
    int n=s.size();
    int i=n-1;

    while (i>=0&&s[i]=='0')s[i]='9',i--;
    if (i>=0)s[i]--;
    else
    {
        for (int j=0;j<n;j++)s[j]='9';
    }
    return s;
}

void solve()
{
    cin>>s;
    cin>>s1>>s2;

    vector<string>pat;
    k=(int)(s2.size()+1)/2;
    for (int i=0;i+k<=(int)s.size();i++){
        pat.push_back(s.substr(i,k));
    }
    aho_corasick ac(pat);

    bool zero=1;
    for (int i=0;i<s1.size();i++)
    {
        if (s1[i]!='0')
        {
            zero=0;
            break;
        }
    }
    ll a,b;
    if (zero==0)
    {

    s1=minus1(s1);
    b=fun(s1,ac);

    }
    else b=0;
    a=fun(s2,ac);
    ll ans=(a-b)%mod;
    if (ans<0)ans+=mod;
    cout<<ans<<"\n";
}

int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc=1;
    //cin>>tc;
    for (int i=1;i<=tc;i++){solve();}
    return 0;
}
/*

 */