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

Poveste şi cerinţă...

După o săptămână de scoală încărcată, lui Gigel i s-a acrit de dat teste şi extemporale. Atât de tare a fost el traumatizat încât a început să viseze cum plouă... cu teste! Mai exact, el s-a visat într-o matrice de dimensiuni $W x H$, în care, iniţial, el se află pe poziţia $(1, 1)$, colţul stânga-jos. Fiecare test se află iniţial la o poziţie $(x{~i~}, y{~i~})$ în matrice, şi “cade” cu o căsuţă pe secunda ($y{~i~}$ scade cu $1$ in fiecare secundă). Din fericire, după această săptămână obositoare, Gigel a învăţat să se ferească destul de bine de teste! Mai exact, el se poate deplasa pe linia $1$ (linia de jos a matricei) cu orice viteză vrea el, dar nu o poate părăsi. Numim o situaţie fericită o aşezare iniţială a testelor în matrice astfel încât Gigel să se poată feri de toate. Trezit din somn, Gigel are doar un lucru in minte: să se pregătească pentru orice situaţie fericită!
 
Aşadar, el va întreabă pentru $W$, $H$ şi $M$ date, câte situaţii fericite există? Două situaţii se consideră diferite dacă există cel puţin o poziţie unde cele două matrici diferă. Cum rezultatul poate fi destul de mare încât să îl sperie pe Gigel, afişaţi doar restul acestuia la împărţirea cu $M$.

h2. Date de intrare

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

De pe prima linie a fişierului de intrare $note2.in$ se citesc 3 numere $$W$$, $$H$$ şi $$M$$, conform spuselor de mai sus.

h2. Date de ieşire

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

În fişierul de ieşire $note2.out$ se va afişeza un singur număr reprezentând numărul de situaţii fericite pentru datele de intrare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ W ≤ 7$
* $10^6^ ≤ M ≤ 10^9^ + 17$, $M$ prim
* Niciun Gigel nu a fost rănit în crearea şi testarea acestei probleme.
 
h2. Subtaskuri
 
table(subtask-uri). |_. Indice |_. Punctaj |_. Restricţii |
| $1$ | $10$ puncte | $1 ≤ W ≤ 7$ |
| $2$ | $10$ puncte | $1 ≤ W ≤ 7$ |
| $3$ | $15$ puncte | $1 ≤ W ≤ 7$ |
| $4$ | $15$ puncte | $1 ≤ W ≤ 7$ |
| $5$ | $20$ puncte | $1 ≤ W ≤ 7$ |
| $6$ | $30$ puncte | $1 ≤ W ≤ 7$ |

h2. Exemplu
table(example). |_. note2.in |_. note2.out |

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

| 3 2 1000000007
| 21

|

h3. Explicaţie
 
...
 

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