一位聪明的学生 Ri Gi Ung 非常擅长物理，但不擅长数学。 他的朋友 Sin Yong Jin 则恰恰相反——他擅长数学，但不擅长物理。 因此，Ri 帮助 Sin 完成物理作业，而 Sin 帮助 Ri 完成数学作业。 不幸的是，今天 Ri 遇到了一道非常非常困难的数学题，他请求 Sin 来解决这个问题。 但今天 Sin 非常忙，所以他也请求你来解决它。 作为 Sin 最好的朋友，你必须解决它。 题目如下： “给定一个整数数组 $\{A_1, A_2, \dots, A_n\}$。 定义一个新的整数数组 $\{B_1, B_2, \dots, B_N, \dots\}$，其公式如下：

$$B_N = \left( \sum_{\substack{i_1+i_2+\dots+i_k=N \\ 1 \le k \le N}} A_{i_1} A_{i_2} \dots A_{i_k} \right) \% \, 1000000007$$

当然，$1 \le i_1, i_2, \dots, i_k \le n$。允许 $u \neq v$ 且 $i_u = i_v$。 例如，$B_3 = A_1 * A_1 * A_1 + A_1 * A_2 + A_2 * A_1 + A_3$。 你必须计算给定整数 $N$ 对应的 $B_N$。” 你能帮助这两位男孩吗？

输入格式

输入文件的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $N$。 $(1 \le n \le 100, 1 \le N \le 100)$ 每个测试用例的下一行包含 $n$ 个以空格分隔的整数。

输出格式

你必须打印一个整数，即问题的结果。

样例

输入 1

1
2 5
3 2

输出 1

495