Ailin just learned to generate all subsets of a set. This procedure is very easy when the number of elements in the set is small, but what if you have very large sets? That’s because she wants to practice what she learned, so the next problem arises: She have an array of N numbers and Q queries, each of them with two values A and B. She selects the values from positions A, A + 1, A + 2, ..., B − 1, B and generates all possible subsets with those values. then she rises by the exponent P to the sum of each subset. Finally she adds the partial results of that operation and write down the answer. Consideranexample: thearrayis[3,5,2,7]andA=1,B=3,P =2,sheselectsvalues3,5,2 and generates all subsets follows: {3}, {5}, {2}, {3, 5}, {3, 2}, {5, 2}, {3, 5, 2}. Now she raises P = 2 to the sum of each subset: 23, 25, 22, 23+5 = 28, 23+2 = 25, 25+2 = 27, 23+5+2 = 210. Finally, she adds partialresults: 23+25+22+28+25+27+210 =8+32+4+256+32+128+1024=1484. She soon realizes that this task is very complicated so she asks you for help in order to calculate the answers. Will you be able to do this? Input There are several cases. The first line of each case contains two numbers N and P (1 ≤ N ≤ 5∗105, 2≤P ≤105). ThenextlinecontainsN positiveintegersai (1≤ai ≤109,1≤i≤N)thearray elements. Then follows another line with the integer Q, the number of queries (1 ≤ Q ≤ 5∗105). The following Q lines each contain two integers A and B (1 ≤ A ≤ B ≤ N). Assume that all the elements ai will be different. Output Print a line for each query. Since the sum may be too high, print the result modulo 109 + 7. Sample Input 42 3527 1 13 Sample Output 1484