Nam is playing with his cards. He has N + 1 cards, numbered from 0 to N. Card number i have a value A_i written on it.

Initially, only card number 0 is on the table. Nam will put N remaining cards 1, 2, ..., N on the table in that order. Each card have two ways to put it on the table: in the left or in the right the cards row currently on the table (see the sample test for better understanding). Therefore there are 2^N ways of putting cards in total. When card valued x is put adjacent card valued y, Nam will gain x * y score more.

Nam plays his own game for fun, so he doesn't care about maximizing or minimizing his final score. He only interested in sum score of all 2^N game he could make. Your task is calculate this number.

Input

The first line is T - the number of test cases. Then T test cases follow.

Each test consists of 2 lines. The first line contains a single positive integer N. The second line contains N + 1 integer numbers A₀, A₁, .., A_N, denoting values are written on cards.

Output

For each test, print the answer. Since the answer may very large, you must print it modulo 10⁹ + 7.

Constraints

1 ≤ T ≤ 20
1 ≤ N ≤ 10⁵
1 ≤ A_i ≤ 10⁵