该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

已经年底了，\(yjj\) 准备买 \(n\) 个相同的年终奖品来犒劳犒劳辛苦训练的集训队成员，\(yjj\) 准备平均分给大家，但是一向贪心的小马却说："我至少要 \(x\) 个！"，随着小马的起哄，大家也都纷纷提出了自己的要求，无奈的 \(yjj\) 只能让大家填收集表收集大家最少需要多少个年终奖品。

现在已知集训队一共有 \(m\) 位成员，第 \(i\)（\(1 \leq i \leq m\)） 位成员至少需要 \(a_i\) 个年终奖品，\(yjj\) 一共买了 \(n\) 个年终奖品，请你告诉 \(yjj\) 一共有多少种分配方案。

奖品可以剩余，并且保证一定存在一种分配方案。

最后的结果取模 \(1000000007\)

Format

Input

第一行输入一个正整数 \(T\)，表示有 \(T\) 次询问。
对于每一次询问，第一行输入两个正整数 \(n,\ m\)，表示有 \(n\) 个年终奖品和 \(m\) 个集训队成员，第二行输入 \(m\) 个整数，第 \(i\) 个整数表示第 \(i\)（\(1 \leq i \leq m\)） 位成员至少需要 \(a_i\) 个年终奖品
对于 \(40 \%\) 的数据，\(1 \leq T \leq 5\)，\(1 \leq n \leq 40\)，\(1 \leq m \leq 10\)，\(0 \leq a_i \leq 10^5\)
对于 \(100 \%\) 的数据，\(1 \leq T \leq 10\)，\(1 \leq n \leq 10^5\)，\(1 \leq m \leq 10^5\)，\(0 \leq a_i \leq 10^5\)
题目保证每组数据一定有至少一组解

Output

输出 \(T\) 行，每行一个整数表示答案

Sample 1

Input

2
3 3
1 1 1
3 3
1 1 0

Output

1
4

Limitation

1s, 1024KiB for each test case.

Hint