h2. Restricţii

* $1 ≤ N, K ≤ 500 000$

* $1 ≤ N, K ≤ 300 000$

* $2 ≤ MOD ≤ 1 000 000 007$
* *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 ≤ 500 000$
* *Subtask 4 (25 puncte):* $1 ≤ N, K ≤ 500 000, MOD = 10^9^ + 7$

* *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
h2. Exemplu