M. Alternating sum
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of $$$n$$$ integers. We define a function $$$f(a)$$$ as follows:

  • $$$f(a)$$$ is the maximum possible sum of elements in $$$a$$$, where no two consecutive elements in $$$a$$$ are selected.

Your task is to compute the sum of $$$f(s)$$$ over all non-empty subsequences $$$s$$$ of the array $$$a$$$. Since this number can be large output it modulo $$$10^9+7$$$. Formally, you need to find:

$$$$$$ \large \sum_{\emptyset \neq s \subseteq a} f(s) \bmod 10^9+7 $$$$$$

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$1\le n\le 10^3$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$,$$$a_2$$$,…,$$$a_n$$$ ($$$1\le a_i\le 2 \cdot 10^5$$$) — the elements of array $$$a$$$.

The sum of $$$n$$$ over all testcases does not exceed $$$10^3$$$.

Output

Output a single integer for each testcase — the sum of $$$f(s)$$$ over all non-empty subsequences $$$s$$$ of the array $$$a$$$ modulo $$$10^9+7$$$.

Example
Input
3
3
3 7 4
5
1 100 5 10 5
10
1 1 2 1 1 2 1 1 1 1
Output
39
1774
3568