h2. Date de intrare

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$.

Fişierul de intrare $preasimplu.in$ va contine pe prima linie 3 numere naturale, $N$, $K$ si $MOD$, cu semnificatiile din enunt, separate prin cate un spatiu.

h2. Date de ieşire

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

În fişierul de ieşire $preasimplu.out$ se va afisa pe prima linie numarul de siruri finale, modulo $MOD$.

h2. Restricţii

* $1 ≤ N, K ≤ 2 000 000$
* $2 ≤ MOD ≤ 1 000 000 007$
 
* *Subtask 1 (10 puncte):* $1 ≤ N ≤ 10, 1 ≤ K ≤ 4$
* *Subtask 2 (10 puncte):* $1 ≤ N ≤ 15, 1 ≤ K ≤ 15$
* *Subtask 3 (10 puncte):* $1 ≤ N, K ≤ 500$
* *Subtask 4 (20 puncte):* $1 ≤ N x K ≤ 2 000 000$
* *Subtask 5 (25 puncte):* $1 ≤ N, K ≤ 2 000 000, MOD = 10^9^ + 7$
* *Subtask 6 (25 puncte):* Restrictii initiale

* *Subtask 1 (10 puncte):* $1 ≤ N ≤ 10, 1 ≤ K ≤ 3$
* *Subtask 2 (10 puncte):* $1 ≤ N, K ≤ 300$
* *Subtask 3 (10 puncte):* $1 ≤ N, K ≤ 1 000$
* *Subtask 4 (20 puncte):* $1 ≤ N x K ≤ 1 000 000$
* *Subtask 5 (30 puncte):* $1 ≤ N ≤ 1 000 000, MOD = 10^9^ + 7$
* *Subtask 6 (20 puncte):* $1 ≤ N ≤ 1 000 000$

h2. Exemplu