Problem 3. Piling Papers

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef complex<int> P;
#define X real()
#define Y imag()
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=3e2+7;
const int D=19;
const int INF=1e18;
const int Mod=1e9+7;
int dp[N][D][D][3];
int a[N];
int pref[N][N];
int query(int i,int l,int r,int c){
    if(l>r){
        return (c==1);
    }
    return dp[i][l][r][c];
}
void add(int &x,int val){
    x+=val;
    if(x>=Mod) x%=Mod;
}
void cal(int n,int st,const string&s){
    int d=sz(s);
    rep(l,0,d-1){
        int sum=0;
        rep(r,0,d-1){
            rep(c,0,2) dp[st][l][r][c]=0;
            if(l==r){
                if(a[st]<s[l]-'0'){
                    dp[st][l][r][0]=2;
                }
                else if(a[st]>s[l]-'0') dp[st][l][r][2]=2;
                else dp[st][l][r][1]=2;
            }
        }
    }
    rep(i,st+1,n){
        rep(l,0,d-1){
            rep(r,l,d-1){
                rep(c,0,2) dp[i][l][r][c]=dp[i-1][l][r][c];
                if(a[i]<s[l]-'0'){
                    rep(c,0,2){
                        add(dp[i][l][r][0],query(i-1,l+1,r,c));
                    }
                }
                else if(a[i]==s[l]-'0'){
                    rep(c,0,2) add(dp[i][l][r][c],query(i-1,l+1,r,c));
                }
                else{
                    rep(c,0,2) add(dp[i][l][r][2],query(i-1,l+1,r,c));
                }
                if(a[i]<s[r]-'0'){
                    add(dp[i][l][r][0],query(i-1,l,r-1,1)+query(i-1,l,r-1,0));
                    add(dp[i][l][r][2],query(i-1,l,r-1,2));
                }
                else if(a[i]==s[r]-'0'){
                    rep(c,0,2) add(dp[i][l][r][c],query(i-1,l,r-1,c));
                }
                else{
                    add(dp[i][l][r][0],query(i-1,l,r-1,0));
                    add(dp[i][l][r][2],query(i-1,l,r-1,1)+query(i-1,l,r-1,2));
                }
            }
        }
    }
}
int cnt(int j,int d){
    int ret=1;
    rep(L,0,d-2){
        rep(c,0,2){
            add(ret,dp[j][0][L][c]);
        }
    }
    add(ret,dp[j][0][d-1][0]+dp[j][0][d-1][1]);
    return ret;
}
signed main(){
    quick
    int n,A,B;
    cin>>n>>A>>B;
    rep(i,1,n) cin>>a[i];
    string B2=to_string(B);
    string A2=to_string(A-1);
//  cal(n,1,B2);debug("cnt",cnt(1,sz(B2)));return 0;
    rep(st,1,n){
        cal(n,st,B2);
    //  debug(st,"st");
        rep(j,st,n){
            pref[st][j]=cnt(j,sz(B2));
    //      cout<<pref[st][j]<<" \n"[j==n];
        }
        cal(n,st,A2);
        rep(j,st,n){
    //      cout<<-cnt(j,sz(A2))<<" \n"[j==n];
            pref[st][j]=(pref[st][j]-cnt(j,sz(A2))+Mod)%Mod;
        }
    }
    /*rep(i,1,n){
        rep(j,i,n){
            cout<<pref[i][j]<<" \n"[j==n];
        }
    }*/
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<pref[l][r]<<"\n";
    }
    return 0;
}