Add or Multiply

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Hussain was feeling very bored in his physics class. Just hearing theorems and formulas about mechanics and electronics makes him utterly sick.
He was very bored so he just started writing random numbers separated by spaces on the pages of his physics book. For example, he wrote the sequence 1 2 3 four times. Each one with different sequence of arithmetic operations between numbers, i.e. he wrote { (1+2+3) , (1+2*3) , (1*2+3) , (1*2*3) } .
He wondered if he wrote a sequence of N positive integers, separated by question marks ?. Each question mark may stand for a plus sign + or a multiplication sign *.
Hussain knows that there are possible 2^(n1) different expressions. He wondered if he wrote each expression and computed their values and summed up all the values. With what value he will end up with? Since answer may be huge, output it modulo 10^9+7
Input
 First line of the input contains a single integer T , denotes the number of testcases. The description of T test cases follow.
 The first line of each testcase contains an integer N denoting how many numbers in the current expression. You may assume that all numbers in the current expression are separated by question marks, and each question mark stands for a plus sign or a multiplication sign.
 The second line of each testcase contains N space separated integers, denoting integers in Hussain's expression.
Output
For each testcase, output a single line containing the sum of results of all possible 2^(n1) different expressions considering that each question mark stands for a plus or a multiplication sign.
Constraints
 1 ≤ T ≤ 500
 1 ≤ n ≤ 100000
 All numbers forming expressions are positive numbers less than 10^{9}
 The sum of n over all test cases won't exceed 10^{6}
Example
Input: 2 3 1 2 4 4 1 1 1 1 Output: 30 20
Explanation
Example case 1. There can be following four expressions.
1 + 2 + 4 = 7 1 + 2 * 4 = 9 1 * 2 + 4 = 6 1 * 2 * 4 = 8
Total sum of results = 30
Author:  deadwing97 
Tags  deadwing97 
Date Added:  1062017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 