Buruiana

Time limit: 1s Memory limit: 256MB Input: buruiana.in Output: buruiana.out

Cerință

Marele zid românesc este format din nn rânduri de cărămizi, numerotate de jos în sus de la 11 la nn, iar fiecare rând conține mm cărămizi, numerotate de la stânga la dreapta de la 11 la mm.

Considerăm cărămida (x,y)(x,y) ca fiind a xx-a cărămidă de pe rândul yy.

Pe acest zid crește o buruiană în felul următor:

  1. Inițial, doar cărămida (1,1)(1,1) este acoperită de buruiană.
  2. În fiecare zi, buruiana va alege o cărămidă acoperită (x,y)(x,y) și va încerca să se răspândească pe o cărămidă neacoperită dintre cărămizile (x1,y)(x-1,y), (x+1,y)(x+1,y) și (x,y+1)(x,y+1).
  3. Dacă buruiana s-a răspândit de pe o cărămidă (x1,y1)(x_1,y_1) pe o altă cărămidă (x2,y2)(x_2,y_2), atunci se va forma o ramură între aceste două cărămizi.

Un exemplu de buruiană pentru n=m=4n=m=4:

Î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 109+710^9+7.

Date de intrare

Pe prima linie a fișierului de intrare buruiana.in se vor afla două numere nn și mm - dimensiunile zidului.

Date de ieșire

Fișierul de ieșire buruiana.out va conține numărul de moduri (modulo 109+710^9+7) în care poate crește buruiana astfel încât să acopere tot zidul.

Restricții și precizări

  • 2n,m10182 \le n,m \le 10^{18};
  • Pentru 99 puncte, n,m4n,m \le 4;
  • Pentru încă 1616 puncte, n=2n=2 și m20m \le 20;
  • Pentru încă 1818 puncte, n=2n=2 și m5 000m \le 5 \ 000;
  • Pentru încă 1212 puncte, n=2n=2 și m106m \le 10^6;
  • Pentru încă 1010 puncte, m106m \le 10^6;
  • Pentru încă 2020 de puncte, m109m \le 10^9;
  • Pentru restul de 1515 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 88 moduri:

Exemplul 2

buruiana.in

6 9

buruiana.out

714900741

Explicație

Răspunsul trebuie afișat modulo 109+710^9+7.

Log in or sign up to be able to send submissions!