You have a sequence of length n. The element of this sequence is seq[i] (i = 1 to n). Now consider a function ∑ seq[i]∗(i−a+1)k foreachibetweenatobinclusive. First line contains T (1 ≤ T ≤ 5) the number of test cases. Then T test cases follow. The first line of each test case contains an integer n (1 ≤ n ≤ 100000). The next line contains n integers seq[1] to seq[n]. Each of these integer is in the range from 0 to 1000000000 inclusive. Next line contains an integer q (q ≤ 10000) the number of queries. Each of the next q lines contains 3 integers k,a,b. k is between 0 to 20 inclusive. 1 ≤ a ≤ b ≤ n. Output For each of the query k,a,b output contains 1 integer in each line the value of F (k, a, b) mod 1000000009. Sample Input 2 10 1245136784 5 137 037 237 337 437 10 3678412451 5 137 037 237 337 437 Sample Output 59 19 231 1013 4683 49 Input F(k,a,b)= Given a sequence of length n you have to calculate F (k, a, b).
2/2 22 141 493 1965