시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 256 MB146330.000%

## 문제

Boy XYZ introduced a simple math function called $\mathit{GLL}$ for an array of integers $S = \{a_1, a_2, \ldots, a_n\}$:

$$\mathit{GLL}(S) = \mathit{GCD}(S) \cdot \mathit{LCM}(S) \cdot \mathit{LCM}(S)\text{.}$$

Here, $\mathit{GCD}(S) = \mathit{GCD}(a_1, a_2, \ldots, a_n)$ is the greatest common divisor of integers $a_1, a_2, \ldots, a_n$, and $\mathit{LCM}(S) = \mathit{LCM}(a_1, a_2, \ldots, a_n)$ is the least common multiple of integers $a_1, a_2, \ldots, a_n$.

For an array consisting of one element, $\mathit{GCD}$ and $\mathit{LCM}$ are equal to that element. For example, $\mathit{GCD}$ of $S = \{x\}$ is $x$. Consider the $\mathit{LCM}$ and $\mathit{GCD}$ of an empty array as $0$.

Now, XYZ is interested in finding the sum of $\mathit{GLL}$ values of all subarrays for a given array $A$, but he finds the problem very hard. Help him calculate the following:

$$\mathit{Answer} = \sum_{S \subseteq A}\mathit{GLL}(S)\text{.}$$

Here, $S \subseteq A$ means that $S$ is a subarray of $A$, that is, the array $A$ with some (possibly zero, possibly all) elements removed.

As the answer can be very large, print it modulo $10^9 + 7$.

## 입력

The first line of input contains $T$, the number of test cases ($1 \le T \le 50$). $T$ test cases follow.

The first line of each test case contains $N$, the number of elements in $A$ ($1 \le N \le 100$). The next line contains $N$ space-separated positive integers: the elements of $A$. The numbers in the array are in the range $[1, 1000]$.

## 출력

For each test case, print the answer on a separate line.

## 예제 입력 1

2
2
2 3
3
2 4 10


## 예제 출력 1

71
2904
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}