Bessie was recently taking a USACO contest and encountered the following problem. Of course, Bessie knows how to solve it. But do you?

Consider a sequence A₁,A₂,…,A_N of length N (1≤N≤5⋅10⁴) consisting solely of integers in the range 1…K (1≤K≤20). You are given Q (1≤Q≤2⋅10⁵) queries of the form [L_i,R_i] 1≤L_i≤R_i≤N). For each query, compute the number of non-decreasing subsequences of ,…, mod 10⁹+7.

A non-decreasing subsequence of A_L,…,A_R is a collection of indices (j₁,j₂,…,j_x) such that L≤j₁<j₂<⋯<j_x≤R and ≤≤⋯≤. Make sure to consider the empty subsequence!

输入描述:

The first line contains two space-separated integers N and K.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains a single integer Q.
The next Q lines each contain two space-separated integers Li and Ri.

输出描述:

For each query [Li,Ri], you should print the number of non-decreasing subsequences of ,…, mod 109+7 on a new line.

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

3
4
20

For the first query, the non-decreasing subsequences are (),(2), and (3). (2,3) is not a non-decreasing subsequence because A2≰A3.

For the second query, the non-decreasing subsequences are (), (4), (5), and (4,5).

备注:

Test cases 2-3 satisfy N≤1000.
Test cases 4-6 satisfy K≤5.
Test cases 7-9 satisfy Q≤105.
Test cases 10-12 satisfy no additional constraints.