Non-Decreasing Subsequences
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[1], A[2], ..., A[n] of length n consisting solely of integers in the range 1...k. You are given q (1 ≤ q ≤ 2 * 10^5) 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 A[li], A[li+1],..., A[ri] mod 10^9 + 7.
A non-decreasing subsequence of A[l],..., A[r] is a collection of indices (j[1], j[2], ..., j[x]) such that l ≤ j[1] < j[2] < ... < j[x] ≤ r and A[j1] ≤ A[j2] ≤ ... ≤ A[jx]. Make sure to consider the empty subsequence!
Input
The first line contains two integers n (1 ≤ n ≤ 5 * 10^4) and k (1 ≤ k ≤ 20). The second line contains n integers A[1], A[2], ..., A[n]. The third line contains a single integer q. Each of the next q lines contains two integers l[i] and r[i].
Output
For each query [l[i], r[i]], you should print the number of non-decreasing subsequences of A[li], A[li+1],... , A[ri] mod 10^9 + 7 on a new line.
Example
For the first query, the non-decreasing subsequences are (), (2) and (3). (2, 3) is not a non-decreasing subsequence because A[2] > A[3].
For the second query, the non-decreasing subsequences are (), (4), (5) and (4, 5).