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 A1,A2,…,AN of length N (1≤N≤5⋅104) consisting solely of integers in the range 1…K (1≤K≤20). You are given Q (1≤Q≤2⋅105) queries of the form [Li,Ri] (1≤Li≤Ri≤N). For each query, compute the number of non-decreasing subsequences of ALi,ALi+1…,ARi mod 109+7.
A non-decreasing subsequence of AL,…,AR is a collection of indices (j1,j2,…,jx) such that L≤j1<j2<⋯<jx≤R and Aj1≤Aj2≤⋯≤Ajx. Make sure to consider the empty subsequence!
Scoring
- 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.
Input Format
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.
Output Format
For each query [Li,Ri], you should print the number of non-decreasing subsequences of ALi,ALi+1…,ARi mod 109+7 on a new line.
Sample Input
5 2
1 2 1 1 2
3
2 3
4 5
1 5
Sample Output
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≰.
For the second query, the non-decreasing subsequences are (), (4), (5), and (4,5).
Problem credits: Benjamin Qi