先考虑 \(1\sim n\) 的时候怎么做，差分一下，只需要求 \(1\sim p\) 就行。先考虑朴素的时候，设 \(f_{i,j,k=0/1/2}\) 表示对于前 \(i\) 个纸片，已经补了 \(j\) 个位置了，当前的数分别小于，等于，大于 \(p\) 数字。
对于题目要求的前插后插很难用这个状态去实现，于是把 \(j\) 给改一下，表示为 \(f_{i,l,r,k=0/1/2}\) 已经补完了 \(l\sim r\) 位，其他的定义跟朴素一样，那这样就很好求出来了。
再考虑一下 \(ql\sim qr\)，提前预处理出来 \(Ans_{ql,qr}\)，把状态 \(i\) 改掉：
\[Ans_{ql,qr}=\sum\limits_{i=1}^m f_{i,m,0/1}+[i\neq1]f_{i,m,2}
\]
时间复杂度为：\(O(n^2\lg^2 p+q)\)
::::info[\(\mathscr{Code:}\)]
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>#define ll long long
// #define int ll
#define pii pair<int,int>
#define ull unsigned long long
using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
char buf[1<<21], *p1=buf,*p2=buf;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define getchar() gc()
ll rd(){ll s=0;char ch=getchar();bool fu=0;while(ch<'0'||ch>'9')ch=='-'?fu=1:0,ch=getchar();while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();return fu?-s:s;
}const int N=310;
int n,a[N],cur[N],cnt;
ll ansA[N][N],A,B,ansB[N][N],f[N][N][3];void getnum(ll a){while(a){cur[++cnt]=a%10;a/=10;}reverse(cur+1,cur+cnt+1);
}static inline ll add(ll a,ll b){return a+b>=mod?a+b-mod:a+b;}
static inline void upd(ll &a,ll b){(a+=b)>=mod?a-=mod:0;}
static inline int calc(ll a,ll b){if(a<b)return 0;if(a==b)return 1;return 2;
}void init(){getnum(A-1);for(int i=1;i<=n;++i){memset(f,0,sizeof(f));for(int j=i;j<=n;++j){for(int l=1;l<=cnt;++l)for(int r=cnt;r>l;--r){if(a[j]>cur[l]){upd(f[l][r][2],f[l+1][r][0]);upd(f[l][r][2],f[l+1][r][1]);upd(f[l][r][2],f[l+1][r][2]);}else if(a[j]==cur[l]){upd(f[l][r][0],f[l+1][r][0]);upd(f[l][r][1],f[l+1][r][1]);upd(f[l][r][2],f[l+1][r][2]);}else{upd(f[l][r][0],f[l+1][r][0]);upd(f[l][r][0],f[l+1][r][1]);upd(f[l][r][0],f[l+1][r][2]);}upd(f[l][r][0],f[l][r-1][0]);upd(f[l][r][calc(a[j],cur[r])],f[l][r-1][1]);upd(f[l][r][2],f[l][r-1][2]);}for(int k=1;k<=cnt;++k)upd(f[k][k][calc(a[j],cur[k])],2);for(int k=1;k<=cnt;++k){upd(ansA[i][j],f[k][cnt][0]);upd(ansA[i][j],f[k][cnt][1]);if(k!=1)upd(ansA[i][j],f[k][cnt][2]);}}}cnt=0;getnum(B);for(int i=1;i<=n;++i){memset(f,0,sizeof(f));for(int j=i;j<=n;++j){for(int l=1;l<=cnt;++l)for(int r=cnt;r>l;--r){if(a[j]>cur[l]){upd(f[l][r][2],f[l+1][r][0]);upd(f[l][r][2],f[l+1][r][1]);upd(f[l][r][2],f[l+1][r][2]);}else if(a[j]==cur[l]){upd(f[l][r][0],f[l+1][r][0]);upd(f[l][r][1],f[l+1][r][1]);upd(f[l][r][2],f[l+1][r][2]);}else{upd(f[l][r][0],f[l+1][r][0]);upd(f[l][r][0],f[l+1][r][1]);upd(f[l][r][0],f[l+1][r][2]);}upd(f[l][r][0],f[l][r-1][0]);upd(f[l][r][calc(a[j],cur[r])],f[l][r-1][1]);upd(f[l][r][2],f[l][r-1][2]);}for(int k=1;k<=cnt;++k)upd(f[k][k][calc(a[j],cur[k])],2);for(int k=1;k<=cnt;++k){upd(ansB[i][j],f[k][cnt][0]);upd(ansB[i][j],f[k][cnt][1]);if(k!=1)upd(ansB[i][j],f[k][cnt][2]);}}}
}inline void Solve(){n=rd(),A=rd(),B=rd();for(int i=1;i<=n;++i)a[i]=rd();init();int q=rd();while(q--){int ql=rd(),qr=rd();
// cout<<"==> "<<ansA[ql][qr]<<" "<<ansB[ql][qr]<<"\n";printf("%lld\n",(ansB[ql][qr]+mod-ansA[ql][qr])%mod);}
}signed main(){// freopen("input.in","r",stdin);// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int T=1;while(T--)Solve();return 0;
}
::::