一.题目链接：

HDU-5145

二.题目大意：

NPY 要在 n 个女朋友里面选取一个去约会，有些女朋友可能会同班.

女朋友编号为 1 ~ n.

为了不引起矛盾，NPY 在一个班里只会选取一名女朋友去约会.

问在第 i ~ j 个女朋友之间选择，有多少种选法（考虑顺序不同，最终答案 % 1000000007）.

三.分析：

先来看选法如何计算

假设在第 i ~ j 中选取，则共有 j - i + 1 个人，在不考虑同班的情况下共有 ( j - i + 1 ) ! 种取法.

假设第 i 班的女朋友数为 cnt[i]

则选取数为   

对于题目描述来说

这是一个典型的离线算法区间处理问题，很明显用莫队算法.

接着考虑的就是莫队算法 while 循环里的操作.

由选取数公式得：加入一个元素，就乘以 ( j - i + 1 ) 并除以 cnt[i].

可惜不能直接除，删除一个元素同理.

那就计算 cnt[i] 的乘法逆元 用费马小定理( Mod 为质数 )就可以做.

初始化打表即可.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)3e4 + 10;
ll Mod = 1000000007;
int a[M];
int cnt[M];
int block;
ll rev[M];
ll res[M];
struct node
{
    int l;
    int r;
    int id;
} s[M];

ll quick_power(ll a, ll b)
{
    ll sum = 1;
    while(b)
    {
        if(b & 1)
            sum = sum * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return sum % Mod;
}



void modui(int n, int m)
{
    int l, r;
    l = 1;
    r = 0;
    ll sum = 1;
    for(int i = 0; i < m; ++i)
    {
        while(r < s[i].r)
        {
            r++;
            cnt[a[r]]++;
            sum = sum * (r - l + 1) % Mod * rev[cnt[a[r]]] % Mod;
        }
        while(r > s[i].r)
        {
            sum = sum * cnt[a[r]] % Mod * rev[r - l + 1] % Mod;
            cnt[a[r]]--;
            r--;
        }
        while(l < s[i].l)
        {
            sum = sum * cnt[a[l]] % Mod * rev[r - l + 1] % Mod;
            cnt[a[l]]--;
            l++;
        }
        while(l > s[i].l)
        {
            l--;
            cnt[a[l]]++;
            sum = sum * (r - l + 1) % Mod * rev[cnt[a[l]]] % Mod;
        }
        res[s[i].id] = sum;
    }
}

int cmp(node a, node b)
{
    if(a.l / block != b.l / block)
        return a.l / block < b.l / block;
    return a.r < b.r;
}

void init()
{
    for(int i = 0; i < M; ++i)
        rev[i] = quick_power(i, Mod - 2);
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(cnt, 0, sizeof(cnt));
        memset(res, 0, sizeof(res));
        int n, m;
        scanf("%d %d", &n, &m);
        block = (int)sqrt(n + 0.5);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for(int i = 0; i < m; ++i)
        {
            int l, r;
            scanf("%d %d", &l, &r);
            s[i].l = l;
            s[i].r = r;
            s[i].id = i;
        }
        sort(s, s + m, cmp);
        modui(n, m);
        for(int i = 0; i < m; ++i)
            printf("%lld\n", res[i]);
    }
    return 0;
}