Bob and Mathematics
Tag(s):

## Medium-Hard

Problem
Editorial
Analytics

Bob was very good at his mathematics. He scored A+ grade in every mathematical subjects. To challenge him his teacher gave him to solve following question :

You are given an array of n positive integers where all integers are less than or equals to 10^6. Now you have to calculate the product of (number of primes + 2) of all subsets of that array. Two subsets of array are considered different if there is an element with index i in one subset such that there is no such element with same index i in other subset.

Lets clear it with an example :

Take an array = [2,4]
Now lets see all subsets
{2} ----> noOfPrimes = 1 So (1+2) = 3
{4} -----> noOfPrimes = 0 So (0+2) = 2
{2,4} -----> noOfPrimes = 1 So (1+2) = 3
{} -----> noOfPrimes = 0 So (0+2) = 2

So final answer is 3*2*3*2 = 36

Note: For empty subset number of primes is 0.

Constraints :
1 <= n <= 10^3
arr[i] <= 10^6
t <= 1000

Input Format :
First line contains t - no of test cases. For each test cases there are two lines. First line contains n - size of array and second line contains array elements.

Output Format :
Print required answer modulo 1000000007 for each test cases.

Tester : Tanmay Patel

SAMPLE INPUT
2
2
2 4
2
4 8
SAMPLE OUTPUT
36
16
Time Limit: 1.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...