1161: 序列

Memory Limit：262 MB Time Limit：2.000 S
Judge Style：Text Compare Creator：
Submit：1 Solved：0

Description

给定一个数字串 S，每次询问这个序列的一个连续子序列的本质不同回文子序列个数。

本质不同的含义是：两个序列不同当且仅当它们的长度不同或存在对应位置不同。

答案可能很大，因此只要输出对1000000007算术取模的值。

Input

第一行包含一个数据组数T。每组数据的格式如下：

第一行包含两个正整数n,m,k，表示序列的长度为n，询问的次数为m，且序列中元素都在[1,k]之间。

接下来一行n个正整数，第i个数表示序列 S的第 i个元素 ci。

接下来m行，每行两个正整数[li,ri]，表示这次询问的子序列为S「LI，RI」


Output

输出m行，每行一个整数，表示这次询问的结果对1000000007算术取模的值。

Sample Input Copy 

1
5 2 2
1 1 2 2 1
1 5
2 4

Sample Output Copy 

7
3

HINT

给出样例一的解释：

第一组询问满足条件的子序列有 {1}, {1,1}, {1,1,1}, {1,2,1}, {1,2,2,1}, {2}, {2,2}，共有7种。

第二组询问满足条件的子序列有 {1}, {2}, {2,2}，共有3种。

数据很弱，请根据题目想出正确方法。 题目保证数据随机生成。另外，区间[li,ri]存在li>ri情况，此时请输出0，同一问题可能询问多次。

数据保证对于10%的数据，N<=10，且存在M=0。对于剩下的90%的数据，存在第一组数据使得n=14.对于20%的数据，存在一组数据使得m=0.

对于100%的数据，n<=50,m<=1000000,k<=1000,t<=10。（其中n,m为本测试点中n,m之和） 


program data;
uses math;
var
f:char;
a:array[1..1000000]of longint;
i,t,n,m,k,p,sumn,summ:longint;
begin
    for f:='1' to '9'  do
    begin
    randomize;
    t:=random(3)+ord(f)-ord('0');
    if t>10 then t:=10;
    sumn:=50; summ:=1000000;
    writeln(t);
    for t:=1 to t do
    begin
      n:=(random(sumn)+3) div 3;
      sumn:=sumn-n;
      m:=min((random(summ)+3) div 3,sqr(n-3));
      summ:=summ-m;
      k:=(ord(f)-ord('0'))*100+random(100);
      writeln(n,' ',m,' ',k);
      for i:=1 to n div 2 do
      begin
        a[i]:=(random(k div 10)+i*random(n)+1)mod k;
        if a[i]=0 then a[i]:=random(k-a[i])+1;
        write(a[i],' ');
      end;
      for i:=n div 2+1 to n do
      begin
        p:=random(2);
        if p=1 then write(a[n-i+1],' ')
               else write((a[random(i-2)+1]+random(i))mod k,' ');
      end;
      writeln;
      for i:=1 to m do
      begin
        p:=random(2);
        a[i]:=(random(i)*i)mod n;
        if a[i]=0 then a[i]:=2+random(n div 2);
        if p=1 then writeln(a[i],' ',a[i]+random(n-a[i]))
               else writeln(a[i],' ',n);
      end;
    end;
    end;
  end.//以上是数据生成代码，自行参考。