In drumul sau spre olimpiadele internationale Arhitectul Ierdnac s-a gandit la urmatoarea problema:

bq. Fie un sir binar b{~i~} cu $N$ elemente. Initial toti bitii sunt setati pe valoarea $0$. Fie $flip(l, r)$ o operatie ce schimba elementele sirului in felul urmator:
{*} Daca rangul elementului *nu* apartine intervalului $[l, r]$, atunci elementul respectiv ramane neschimbat;
{*} Altfel, elementul isi schimba valoarea (adica din $0$ devine $1$ si din $1$ devine $0$).

bq. Fie un sir binar b{~i~} cu $N$ elemente. Initial toti bitii sai sunt setati pe valoarea $0$. Fie $flip(l, r)$ o operatie ce schimba elementele sirului in felul urmator:
{*} Daca rangul elementului la care ne referim *nu* apartine intervalului $[l, r]$, atunci elementul respectiv ramane neschimbat;
{*} Altfel, elementul isi schimba valoarea (adica din $0$ devine $1$ si, respectiv, din $1$ devine $0$).

Se cere numarul de siruri finale ce se pot obtine daca se efectueaza fix $K$ operatii de $flip$ la alegere. Deoarece raspunsul poate fi destul de mare, se cere afisarea acestuia modulo $10^9^ + 7$.
Vazut fiind acolo, acesta s-a intalnit cu Bossu' Frumosu' si i-a povestit despre problema. Acesta a raspuns imediat prin faimoasa deja replica "Prea simplu!" si a sugerat mai multe metode de a complica artificial problema. Dupa lungi deliberari, comisia a decis - numarul de solutii va trebui afisat modulo un numar natural nenul $MOD$ arbitrar!

h2. Restricţii

* $1 ≤ T ≤ 250$

* $1 ≤ N, K ≤ 300 000$
* $2 ≤ MOD ≤ 1 000 000 007$

* Suma tuturor $N$-urilor din fisier $≤ 600 000$

* *Subtask 1 (10 puncte):* $1 ≤ N ≤ 8, 1 ≤ K ≤ 4$ - Fiecare test din grupa are T = 32 si fiecare pereche $(N, K)$ apare maxim o data in input
* *Subtask 2 (15 puncte):* $1 ≤ N ≤ 14, 1 ≤ K ≤ 14$ - Fiecare test din grupa are T = 52 si fiecare pereche $(N, K)$ apare maxim o data in input (totusi, testele nu sunt maxime cu aceasta proprietate - altfel ar fi trebuit marita prea mult limita de timp pentru un astfel de subtask mic)
* *Subtask 3 (25 puncte):* $1 ≤ N x K ≤ 600 000$
* *Subtask 4 (25 puncte):* $1 ≤ N, K ≤ 300 000, MOD = 10^9^ + 7$
* *Subtask 5 (25 puncte):* Restrictii initiale

* *Subtask 1 (10 puncte):* $1 ≤ N ≤ 8, 1 ≤ K ≤ 4$ - Fiecare test din grupa are $T = 32$ si fiecare pereche $(N, K)$ apare maxim o data in input (Feedback testul $2$)
* *Subtask 2 (15 puncte):* $1 ≤ N ≤ 14, 1 ≤ K ≤ 14$ - Fiecare test din grupa are $T = 52$ si fiecare pereche $(N, K)$ apare maxim o data in input (totusi, testele grupei nu sunt maxime cu aceasta proprietate - altfel ar fi trebuit marita mult prea mult limita de timp pentru un astfel de subtask mic) (Feedback testul $3$)
* *Subtask 3 (25 puncte):* $1 ≤ N x K ≤ 300 000$, iar suma dupa toate testele din fisierul curent din $N x K ≤ 1 200 000$ (Feedback testele $7$ si $8$)
* *Subtask 4 (25 puncte):* $1 ≤ N, K ≤ 300 000$, $MOD = 10^9^ + 7$ (Feedback testele $11$ si $15$)
* *Subtask 5 (25 puncte):* Restrictii initiale (Feedback testele $17$, $19$ si $20$)

h2. Exemplu