Arjit is a great coder. He is one of the best all over world. He can solve almost any question.
Arjit's heart falls for a girl Milinda. She came to Arjit with a question.
Given an array Arr, where:
Arr = {X, A[0] * X, A[0] * A[1] * X, A[0] * A[1] * A[2] * X, ... }
where A[i] denotes a number between 1 and 10⁶.

We all know about the notation:

Milinda asks Arjit to find the value of Q.

Arjit is unable to concentrate on the question due to Milinda. Please help him solve this problem.

Input Format:
The first line contains T, the number of test cases.
Each test case consists of 2 lines.
The first line contains N, the size of array Arr.
The second line contains N space separated integers.

Output Format:
For each test case in the input, print the output to MIlinda's query i.e. Q.
Since the answer can be very large output it modulo 10^9 + 7.

Constraints
1 <= T <= 10
1 <= N <= 10⁵
1 <= X <= 10⁶
1 <= Arr[i] <= 10⁹ + 7
Since the values in array Arr can grow quite large the values given will be modulo 10⁹+7

Subtask 1:
T = 10, 1 <= N <= 100 - 25 points

Subtask 2:
Original constraints - 75 points