问题 G: Make 2

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 ��>1ai>1, then decrease ��ai by $1$, and add $1$ to ��−1ai−1 and ��+1ai+1.

A sequence consisting of $n$ positive integers is considered good if it is possible to make ��=2ai=2 for each $1\le i\le 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 (��,��)(xi,yi) which requires ���=��axi=yi.

It can be proven that the answer is finite. Output the answer modulo 109+7109+7.

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≤�≤10181≤n≤1018, $0\le m\le \min (n,100)$).

The next $m$ lines each contains two integers. The $i$-th line contains ��,��xi,yi (1≤�1<�2<⋯<��≤�1≤x1<x2<⋯<xm≤n, 1≤��≤1091≤yi≤109).

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

1
2
158552999