Problem H
Sum
Input: Standard Input
Output: Standard Output
You have a sequence of length n. The element of this sequence is seq[i] (i = 1 to n).
Now consider a function
F(k,a,b) = ∑seq[i]*(i-a+1)k for each i between a to b inclusive.
Given a sequence of length n you have to calculate F(k,a,b).
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.
For each of the query k,a,b output contains 1 integer in each line the value of F(k,a,b)mod 1000000009.
|
2 10 1
2 4 5 1 3 6 7 8 4 5 1
3 7 0
3 7 2
3 7 3
3 7 4
3 7 10 3
6 7 8 4 1 2 4 5 1 5 1
3 7 0
3 7 2
3 7 3
3 7 4
3 7 |
59 19 231 1013 4683 49 22 141 493 1965 |
Problemsetter: Abdullah al Mahmud
Special Thanks: Manzurur Rahman Khan