Has it ever happened to you that, having worked on a problem for a long time, it starts to pop up in your conscious mind when you least expect it? Just the other day I was singing that old song that goes “Something in the way she moves. . . ”, but before I knew it, I replaced part of the lyrics with “Sum-thing in the way she woos me...”. The only explanation I have for this is that I had been working recently on a curious mathematical problem concerning sums. It goes something like this: Consider a list A with n positive integers, A1, A2, A3, . . . , An. A function S is defined as follows, for 1 ≤ k ≤ n: ∑n ∑n ∑n ∑n S(k)=2k−1 ··· A A A ···A i1=1 i2=i1+1 i3=i2+1 ik=ik−1+1 For example, if A = (1, 2, 3), then the possible values of S are: S(1) = 1+2+3=6 S(2) = 2·((1·2)+(1·3)+(2·3))=2(2+3+6)=22 S(3) = 4·(1·2·3)=4·6=24 What the problem asks is, given the list A, find the sum: ∑n Φ= S(k) k=1 Input Input starts with an integer T, the number of test cases. Each test case starts with an integer n in the first line. The second line of each case contains n positive integers, separated by spaces, that form the set A. T ≤10;1≤n≤105;1≤Ai ≤109 for1≤i≤n Output For each test case, print the value of Φ, modulo 1000000009 (109 + 9) on a single line. Sample Input 2 3 123 5 2 3 5 7 11 Sample Output 52 66412 i1 i2 i3 ik