Boy XYZ 引入了一个简单的数学函数 $GLL$，用于处理整数数组 $S = \{a_1, a_2, \dots, a_n\}$：

$$GLL(S) = GCD(S) \cdot LCM(S) \cdot LCM(S)$$

其中，$GCD(S) = GCD(a_1, a_2, \dots, a_n)$ 是整数 $a_1, a_2, \dots, a_n$ 的最大公约数，$LCM(S) = LCM(a_1, a_2, \dots, a_n)$ 是整数 $a_1, a_2, \dots, a_n$ 的最小公倍数。

对于仅包含一个元素的数组，其 $GCD$ 和 $LCM$ 等于该元素本身。例如，$S = \{x\}$ 的 $GCD$ 为 $x$。空数组的 $LCM$ 和 $GCD$ 视为 $0$。

现在，XYZ 对给定数组 $A$ 的所有子序列的 $GLL$ 值之和感兴趣，但他觉得这个问题很难。请帮他计算以下值：

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

这里 $S \subseteq A$ 表示 $S$ 是 $A$ 的一个子序列，即从数组 $A$ 中删除若干（可能为零，可能全部）元素后得到的数组。

由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量（$1 \le T \le 50$）。接下来是 $T$ 个测试用例。 每个测试用例的第一行包含 $N$，表示数组 $A$ 的元素个数（$1 \le N \le 100$）。下一行包含 $N$ 个空格分隔的正整数，即数组 $A$ 的元素。数组中的数字范围在 $[1, 1000]$。

输出格式

对于每个测试用例，在单独的一行中输出答案。

样例

输入 1

2
2
2 3
3
2 4 10

输出 1

71
2904