!problema/note2?note1.jpg 200x200! !problema/note2?note2.jpg 200x200!
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ă!
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$.
