Dana je \(n \times n\) šahovska ploča gdje vi i kompjuter alternirajući postavljate bijele (vi) i crne (kompjuter) topove. Dok vi postavljate topa, morate paziti da ne napadnete drugoga. Dva topa napadaju jednog drugog ako dijele isti red ili stupac bez obzira na boju.

Ispravan potez je postavljanje topa na poziciju \((r, c)\) tako da ne napada nijednog drugog topa.

Vi počinjete prvi, a kada napravite ispravan potez na poziciju \((r, c)\), kompjuter će postaviti topa na poziciju zirclano preko iskodišta, na poziciju \((n+1-r, n+1-c)\) neovisno o tome napada li taj crni top nekog i neovisno o tome nalazi li se netko tamo.

Već ste postavili \(k\) poteza (te je kompjuter pokušao postaviti svoje poteze.) i morate nastaviti igrati igru dok više ne postoji ispravnih poteza. Koliko završnih konfiguracija postoji ako nastavite igru nakon tih \(k\) poteza?

Zbog toga što broj može biti velik, ispišite ostatak pri djeljenju njega sa \(107071.\) Oprez na modulo.

Dvije konfiguracije su različite ako postoji koordinata \((r, c)\) koja ima topa u jednoj konfiguraciji, a u drugoj nema ili ako je top na toj poziciji drugačije boje.

Ulazni podatci:

U prvom retku nalazi se broj \(t\) (\(1 \leq t \leq 2000\)), broj testnih primjera.

U prvom retku svakog testnog primjera nalaze se brojevi \(n\) (\(1 \leq n \leq 10^{18}\)) i \(k\) (\(0 \leq k \leq \min(10^5, \lceil \frac{n}{2}\rceil)\)), veličina ploče te broj poteza koje ste odigrali.

Idućih \(k\) redova sadržavaju dva broja \(r_i\) i \(c_i\), označavajući \(i\)-ti potez koji ste napravili.

Garantirano je da su svi potezi ispravni.

Izlazni podatci:

Ispišite traženi broj iz zadatka.

Podzadatci

Ulaz primjera 1

1
5 1
3 1

Izlaz primjera 1

16

Ulaz primjera 2

1
4 1
1 1

Izlaz primjera 2

4

Pojašnjenje prvog probnog primjera

U početku imamo:

.....
.....
W...B
.....
.....

Iz čega dobivamo:

...W. ...W. ...B. ...B.
..W.. ..B.. ..W.. ..B..
W...B W...B W...B W...B
..B.. ..W.. ..B.. ..W..
.B... .B... .W... .W...

..W.. ..W.. ..W.. ..W..
...W. ...B. .W... .B...
W...B W...B W...B W...B
.B... .W... ...B. ...W.
..B.. ..B.. ..B.. ..B..

..B.. ..B.. ..B.. ..B..
...W. .B... ...B. .W...
W...B W...B W...B W...B
.B... ...W. .W... ...B.
..W.. ..W.. ..W.. ..W..

.W... .W... .B... .B...
..W.. ..B.. ..W.. ..B..
W...B W...B W...B W...B
..B.. ..W.. ..B.. ..W..
...B. ...B. ...W. ...W.

Slika drugog probnog primjera