这题说的是个了n个数字 然后 在L 和R 区间内的数字的排列有多少种方案，
这里我们通过 将 这n长度的字符串 分成sqrt(n) 块然后 一个属性 他们的l 属于 那个快 以这个为第一关键字 ，然后 在按照R 为 第二个关键字，然后sort 每个查询区间
我们知道 当L他们属于一块内的时候 ， R 是逐渐递增的 ，那么 转移了 sqrt(n)*a+n个 然后以此方案接近复杂度接近n^(1.5)
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn = ;
const LL mod = ;
struct seg{
int L,R,id;
}P[maxn];
int b[maxn];
void gcd(LL a, LL b, LL &d, LL &x, LL &y ){
if(b==){
d=a; x=; y=;
}else{
gcd(b,a%b,d,y,x); y-=x*(a/b);
}
}
LL inv( LL a){
LL d, x,y;
gcd(a,mod,d,x,y);
return d==?(x+mod)%mod:-;
}
LL A[maxn],ans[maxn],num[maxn],aa,niA[maxn];
int C[maxn];
bool cmp(seg A, seg B){
return b[A.L]==b[B.L]?A.R<B.R:b[A.L]<b[B.L];
}
void update(int x, int add){
aa= (aa * niA[ num[x] ] )%mod;
num[x]+=add;
aa= (aa * A[num[x] ] )%mod;
}
void solve(int m){
memset(num,,sizeof(num));
aa=;
LL L=, R=;
for(int i=; i<m; i++){
while(R<P[i].R){
R++;
update(C[R],);
}
while(R>P[i].R){
update(C[R],-);R--;
}
while(L<P[i].L){
update(C[L],-);L++;
}
while(L>P[i].L){
L--;
update(C[L],);
}
ans[ P[i].id ]=(inv(aa)*A[ P[i].R-P[i].L+ ])%mod;
}
for(int i=; i<m; i++){
printf("%I64d\n",ans[i]);
}
}
int main()
{
A[]=; niA[]=inv();
for(LL i=; i<maxn-; i++){ A[i]=(A[i-]*i)%mod;
niA[i] = inv(A[i]);
}
int cas;
scanf("%d",&cas);
for(int cc=; cc<=cas; ++cc){
int n,m;
scanf("%d%d",&n,&m);
int boloc=sqrt(n+0.5);
for(int i=; i<=n; i++){
b[i]=(i-)/boloc+;
}
for(int i=; i<=n; i++)scanf("%d",&C[i]);
for(int i=; i<m; i++){
P[i].id=i; scanf("%d%d",&P[i].L,&P[i].R);
}
sort(P,P+m,cmp);
solve(m);
}
return ;
}