Cerință
Marele zid românesc este format din rânduri de cărămizi, numerotate de jos în sus de la la , iar fiecare rând conține cărămizi, numerotate de la stânga la dreapta de la la .
Considerăm cărămida ca fiind a -a cărămidă de pe rândul .
Pe acest zid crește o buruiană în felul următor:
- Inițial, doar cărămida este acoperită de buruiană.
- În fiecare zi, buruiana va alege o cărămidă acoperită și va încerca să se răspândească pe o cărămidă neacoperită dintre cărămizile , și .
- Dacă buruiana s-a răspândit de pe o cărămidă pe o altă cărămidă , atunci se va forma o ramură între aceste două cărămizi.
Un exemplu de buruiană pentru :
În câte moduri poate crește buruiana astfel încât să acopere tot zidul? Două moduri de creștere se consideră diferite dacă există o ramură în primul mod care nu există în al doilea, sau vice-versa.
Deoarece răspunsul poate fi foarte mare, afișați restul acestuia la împărțirea prin .
Date de intrare
Pe prima linie a fișierului de intrare buruiana.in
se vor afla două numere și - dimensiunile zidului.
Date de ieșire
Fișierul de ieșire buruiana.out
va conține numărul de moduri (modulo ) în care poate crește buruiana astfel încât să acopere tot zidul.
Restricții și precizări
- ;
- Pentru puncte, ;
- Pentru încă puncte, și ;
- Pentru încă puncte, și ;
- Pentru încă puncte, și ;
- Pentru încă puncte, ;
- Pentru încă de puncte, ;
- Pentru restul de de puncte, nu se impun restricții suplimentare.
Exemplul 1
buruiana.in
2 3
buruiana.out
8
Explicație
Buruiana poate să crească în următoarele moduri:
Exemplul 2
buruiana.in
6 9
buruiana.out
714900741
Explicație
Răspunsul trebuie afișat modulo .