Vasya 厌倦了子串（substrings）和子序列（subsequences）之间的混淆。因此，他想知道对于一个随机生成的字符串 $s$，其所有不同的子序列集合与所有不同的子串集合相等的概率是多少。

Vasya 按以下方式生成字符串：字符串的 $n$ 个字符中的每一个都是独立地从相同的分布中生成的。字符串的第 $i$ 个字符等于英文字母表中第 $j$ 个字母的概率为：

$$\frac{w_j}{\sum_{k=1}^m w_k}$$

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$) —— 测试用例的数量。

每个测试用例的描述包含两行。

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^9, 1 \le m \le 26$) —— 字符串的字符数以及用于生成字符串的字母数量。

第二行包含 $m$ 个整数 $w_i$ ($1 \le w_i, \sum_{i=1}^m w_i \le 10^9$)。

输出格式

如果第 $i$ 个测试用例的答案为最简分数 $\frac{P}{Q}$，则输出 $P \cdot Q^{-1} \pmod{10^9+7}$。每个测试用例的答案占一行。

样例

输入样例 1

3
3 1
5
2 5
1 2 3 4 5
5 5
1 2 3 4 5

输出样例 1

1
1
819476549