Moisil++ 2023 Clasele 11-12 Mirror | Buruiana

Cerință

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

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

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

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

Un exemplu de buruiană pentru $n=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 $10^9+7$.

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• $2 \le n,m \le 10^{18}$;
• Pentru $9$ puncte, $n,m \le 4$;
• Pentru încă $16$ puncte, $n=2$ și $m \le 20$;
• Pentru încă $18$ puncte, $n=2$ și $m \le 5 \ 000$;
• Pentru încă $12$ puncte, $n=2$ și $m \le 10^6$;
• Pentru încă $10$ puncte, $m \le 10^6$;
• Pentru încă $20$ de puncte, $m \le 10^9$;
• Pentru restul de $15$ 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 $8$ moduri:

Exemplul 2

buruiana.in

6 9

buruiana.out

714900741

Explicație

Răspunsul trebuie afișat modulo $10^9+7$.