Fişierul intrare/ieşire:	note2.in, note2.out	Sursă	ad-hoc
Autor		Adăugată de	Livia Magureanu •livlivi
Timp execuţie pe test	0.3 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Note2

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) cu 1 ≤ x_i ≤ W si 1 ≤ y_i ≤ H în matrice, şi “cade” cu o căsuţă pe secunda (y_i scade cu 1 in fiecare secundă). Testele de pe linia 1 (cele cu y_i = 1) dispar in loc sa cada. 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 sau sa sara peste un test. Practic, intre oricare 2 caderi consecutive ale testelor, sau inainte de prima cadere, el poate sa se deplaseze din casuta in care se afla, intr-o casuta vecina la stanga sau la dreapta de oricate ori. 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.

Date de intrare

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

Date de ieşire

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

Restricţii

• 1 ≤ W ≤ 7
• 10⁶ ≤ M ≤ 10⁸, M prim
• Niciun Gigel nu a fost rănit în crearea şi testarea acestei probleme.

Subtaskuri

Exemplu

Cum se trimit solutii?