Make 2

Problem Description

For a sequence $a$ consisting of $n$ positive integers, you can perform the following operation several times:

• Choose an index $i$ which satisfies $1< i< n$ and $a_i> 1$, then decrease $a_i$ by $1$, and add $1$ to $a_{i-1}$ and $a_{i+1}$. A sequence consisting of $n$ positive integers is considered good if it is possible to make $a_i=2$ for each $1\leq i\leq n$, by using several (possibly, zero) such operations. Now you need to calculate the number of good sequences that satisfy $m$ constraints, the $i$-th constraint can be represented as a pair $(x_i, y_i)$ which requires $a_{x_i}=y_i$. It can be proven that the answer is finite. Output the answer modulo $10^9+7$.

Input

The first line contains a single integer $T$ ($1\le T\le 10$), denoting the number of test cases. For each test case, the first line contains two integers $n,m$ ($1\le n\le 10^{18}$, $0\le m\le \min(n,100)$). The next $m$ lines each contains two integers. The $i$-th line contains $x_i,y_i$ ($1\le x_1< x_2< \cdots < x_m\le n$, $1\le y_i\le 10^9$).

Output

For each test case, output one line with an integer denoting the answer modulo $10^9+7$.

Sample Input

3
3 1
2 2
5 2
1 2
5 1
114514 0

Sample Output

1
2
158552999

Source

2023“钉耙编程”中国大学生算法设计超级联赛（10）