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 consisting solely of integers in the range 1...k. 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!

Input

The first line contains two integers n (1 ≤ n ≤ 5 * 104) and k (1 ≤ k ≤ 20). The second line contains n integers A1, A2, ..., An. The third line contains a single integer q. Each of the next q lines contains two integers li and ri.

Output

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.

Example

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).