SOLVE
LATER
Problems never seem to end for Mike and Monk, and this time they need to deal with a really old foe of theirs i.e Charles Forstman. Forstman is a rich rich man, and is rather extremely good with numbers. This might not be the case with Mike and Monk thus, to get the better of them, Forstman gives them the following task :
You have been given an integer K expressed as the product of N integers \(A[1],A[2],A[3]...A[N]\). In short, \(K=\prod_{i=1}^{N} (A[i]) \).
Now, we define 2 functions :
\( F(x) \) = \( \sum_{d|x} \space G(d) \)
\( G(x) \) = \( \sum_{d|x} \space d \)
\( d | x \) denotes all integers d, that divide x evenly.
Given the array A, you need to find \(F(K)\). As the answer can be rather large find it Modulo \(10^9+7\). Can you help Monk ?
Input Format :
The first line contains a single integer T denoting the number of test cases in a single input file. Each test case consists of 2 lines, and is as follows :
The first line of each test case consists of a single integer N denoting the size of array A. The next line consists of N space separated integers, where the \(i^{th}\) integer denotes \(A[i]\).
Output Format :
For each test case, print the required answer on a new line. As the may be rather large, print it Modulo \(10^9+7\).
Constraints :
\( 1 \le T \le 5 \)
\( 1 \le N \le 500 \)
\( 2 \le A[i] \le 10^9 \), where \( 1 \le i \le N \)
Subtasks :
For 20% of the points :
\( 1 \le N \le 5 \)
\( 1 \le A[i] \le 100 \)
For 100% of the points :
Original constraints
\( 3 \times 3 \times 2 \times 3 \) = \(54\). The divisors of \(54\) are :
1. \(G(1)\) = 1
2. \(G(2)\) = 3
3. \(G(3)\) = 4
6. \(G(6)\) = \(12\).
9. \(G(9)\) = \(13\)
\(18\). \(G(18)\) = \(39\)
\(27\). \(G(27)\) =\(40\)
\(54\). \(G(54)\) = \(120\)
Thus , \(F(54)\) = \(G(1)+G(2)+G(3)+G(6)+G(9)+G(18)+G(27)+G(54)\)= \(1+3+4+12+13+39+40+120\) = \(232\)