Fişierul intrare/ieşire:note2.in, note2.outSursăad-hoc
AutorAdăugată delivliviLivia Magureanu livlivi
Timp execuţie pe test0.6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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 (xi, yi) cu 1 ≤ xi ≤ W si 1 ≤ yi ≤ H în matrice, şi “cade” cu o căsuţă pe secunda (yi scade cu 1 in fiecare secundă). Testele de pe linia 1 (cele cu yi = 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
  • 106 ≤ M ≤ 108, M prim
  • Niciun Gigel nu a fost rănit în crearea şi testarea acestei probleme.

Subtaskuri

IndicePunctajRestricţii
110 puncte1 ≤ W x H ≤ 20
210 puncte1 ≤ W X H ≤ 50
315 puncte1 ≤ H ≤ 100
415 puncte1 ≤ H ≤ 1000
520 puncte1 ≤ H ≤ 100 000
630 puncte1 ≤ H ≤ 108

Exemplu

note2.innote2.out
3 2 666013
21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?