preasimplu

Prea Simplu!

== include(page="template/taskheader" task_id="preasimplu") ==

Poveste şi cerinţă...

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 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!
 
Din nefericire, Bossu' Frumosu' nu stia sa solutioneze noua problema, dar Arhitectul Ierdnac exclama imediat "Da' stai dom'le ca e usoara!" si, astfel, problema a ajuns in setul de probleme Junior Challenge 2016.

h2. Date de intrare

Fişierul de intrare $preasimplu.in$ ...

Fişierul de intrare $preasimplu.in$ va contine pe prima linie un numar natural nenul $T$, semnificand numarul de teste ce vor urma. Apoi, testele vor fi descrise pe cate o linie de forma $N K MOD$.

h2. Date de ieşire

În fişierul de ieşire $preasimplu.out$ ...

Fişierul de ieşire $preasimplu.out$ va contine $T$ linii, fiecare continand raspunsul pentru testul corespunzator din input.

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 (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
table(example). |_. preasimplu.in |_. preasimplu.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|1
2 1 1000
| 3

|
h3. Explicaţie

...

Sirul initial este $0 0$.
 
Folosind operatia $flip(1, 1)$, se obtine sirul $1 0$;
Folosind operatia $flip(2, 2)$, se obtine sirul $0 1$;
Folosind operatia $flip(1, 2)$, se obtine sirul $1 1$.
 
Asadar, se pot obtine $3$ siruri.

== include(page="template/taskfooter" task_id="preasimplu") ==