传送门：https://codeforces.com/contest/1051/problem/E

题意：

　　把一个数分成许多小段，每一段的值在L和R间。问有多少种分法。

思路 ：

　　首先，需要快速处理出每个位子 ，最近和最远可以组合的区间。如何处理这个区间，由于时限比较紧张，可以用哈希的方法，因为是长度固定，所以可以用二分确定两端长度前缀，再比较大小的方法。当然哈希要用比较好的双哈希。

　　然后，我们可以从后往前dp，每个位子的答案 = 这个位子对应区间的值的和。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue

typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair pll;
typedef pair pii;
typedef pair p3;

//priority_queue q;//这是一个大根堆q
//priority_queue,greater >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n'

#define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行 #define REP(i , j , k) for(int i = j ; i < k ; ++i) #define max3(a,b,c) max(max(a,b), c); #define min3(a,b,c) min(min(a,b), c); //priority_queue, greater >que;

const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = ;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601;

template
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
}
/*-----------------------showtime----------------------*/
const int maxn = 1e6+;
const int base = ;
const int base2 = ;
const int MOD = 1e9+;
//const ll MOD2 = 1e16+17;
int dple[maxn],dpri[maxn];
int lenle,lenri;
ll dp[maxn],sum[maxn];
struct hash
{
char s[maxn];
ll h1[maxn],qp1[maxn];
ull h2[maxn],qp2[maxn];
ll p1[maxn],p2[maxn],len,val1[maxn],val2[maxn];

            void init()  
            {  
                h1\[\]=val1\[\]=;  
                qp1\[\]=p1\[\]=;  
                len=strlen(s+);  
                for(int i=;i<=len;i++)  
                {  
                    qp1\[i\]=(qp1\[i-\]\*base)%MOD;  
                    h1\[i\]=(h1\[i-\]\*base%MOD+s\[i\])%MOD;  
                }

                h2\[\]=val2\[\]=;  
                qp2\[\]=p2\[\]=;  
                for(int i=;i<=len;i++)  
                {  
                    qp2\[i\]=(qp2\[i-\]\*base2);  
                    h2\[i\]=(h2\[i-\]\*base2+s\[i\]);  
                }  
            }  
            ll get\_hash1(int l,int r)  
            {  
                return ((h1\[r\]-h1\[l-\]\*qp1\[r-l+\])%MOD +MOD )% MOD;  
            }  
            ull get\_hash2(int l,int r)  
            {  
                return ((h2\[r\]-h2\[l-\]\*qp2\[r-l+\]));  
            }  
        }A,L,R;

        bool checkle(int l1, int r1) {  
                int le = l1, ri = r1;  
                while(le <= ri){  
                    int mid = (le + ri) >> ;  
                    if(A.get\_hash1(le,mid) == L.get\_hash1(le-l1+,mid-l1+)  && A.get\_hash2(le,mid) == L.get\_hash2(le-l1+,mid-l1+)){  
                        le = mid+;  
                    }  
                    else ri = mid - ;  
                }  
                if(le == r1 + ) return true;  
                return A.s\[le\] >= L.s\[le - l1 + \];  
        }

        bool checkri(int l1,int r1) {  
                int le = l1, ri = r1;

                while(le <= ri){  
                    int mid = (le + ri) >> ;

                    if(A.get\_hash1(le,mid) == R.get\_hash1(le-l1+,mid-l1+) &&A.get\_hash2(le,mid) == R.get\_hash2(le-l1+,mid-l1+) ){  
                        le = mid+;  
                    }  
                    else ri = mid-;  
                }  
                if(le == r1 + ) return true;  
                return A.s\[le\] <= R.s\[le - l1 + \];  
        }

int main(){
scanf("%s%s%s", A.s + , L.s + ,R.s + );
A.init(); L.init(); R.init();

        ll len = A.len;  
        int n = len;  
        lenle = L.len; lenri = R.len;  
        for(int i=; i<=n; i++){  
            int le = i, ri = n;  
            dple\[i\] = -; dpri\[i\] = -;  
            if(A.s\[i\] == '') {  
                    if(L.s\[\] == '') dple\[i\] = i,dpri\[i\] = i;  
                    else dple\[i\] = -,dpri\[i\] = -;  
                    continue;  
            }

            if(i + lenle - <= n &&  checkle(i, i + lenle - )) dple\[i\] = i + lenle - ;  
            else if(i + lenle<=n)dple\[i\] = i + lenle;

            if(i + lenri - <= n&& checkri(i, i + lenri -)) dpri\[i\] = i + lenri - ;  
            else dpri\[i\] = min(n,i+lenri-);

        }

        sum\[n+\] = ;  
        for(int  i=n; i>=; i--){  
            int pl = dple\[i\] + ,pr = dpri\[i\] + ;

            dp\[i\] = ((sum\[pl\] - sum\[pr + \] ) % mod + mod )%mod;  
            sum\[i\] = (sum\[i+\] + dp\[i\]) % mod;  
        }

        cout<<dp\[\]<<endl;  
        return ;  

}