造 2

中文题目为机翻，原题目请参考英文题面

对于由 $n$ 正整数组成的序列 $a$ ，可以多次进行以下操作：

选择一个满足 $1 < i < n$ 且 $a_i>1$ 的索引 $i$ ，然后将 $a_i$ 减少 $1$ ，并在 $a_{i-1}$ 和 $a_{i+1}$ 上加上 $1$ 。

如果可以通过几次（可能是零）这样的运算，使 $a_i = 2$ 每 $1 \leq i \leq n$ ，那么由 $n$ 正整数组成的序列就被认为是好序列。

现在，您需要计算满足 $m$ 约束的良好序列的数量，第 $i$ 个约束可以表示为一对 $(x_i,y_i)$ ，要求 $a_{x_i} = y_i$ 。

可以证明答案是有限的。输出模 $10^9 +7$ 的答案。

输入

第一行包含一个整数 $T \: (1 \leq T \leq 10)$ ，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n,m \: (1 \leq n \leq 10^{18}, 0 \leq m \leq min(n,100))$。

接下来的 $m$ 行各含两个整数。第 $i$ 行包含 $x_i,y_i \: (1 ≤ x_1 < x_2 < \dots < x_m \leq n, 1 \leq y_i \leq10^9)$。

对于每个测试用例，输出一行，用一个整数表示答案模 $10^9 +7$ 的结果。

1
2
158552999