Enunt

Carmen, piticul de gradina vrea sa meargă în vizita la piticul Tulosba. Pentru a ajunge la Tulosba, Carmen trebuie sa meargă printr-o rețea de N galerii, fiecare alcătuită din M sectoare.

Rețeaua poate fi reprezentată printr-un tablou cu N linii, numerotate de la 1 la N și M coloane, numerotate de la 1 la M . Carmen ocupă sectorul 1 al galeriei 1. Tulosba ocupă sectorul M al galeriei 1.

La galeria n se termina rețeaua și începe gradina unde sunt niște copii răi care vor sa-l spargă pe Carmen cu bâtele de Baseball.

Dacă sectorul curent a lui Carmen este (i,j), atunci se poate deplasa:

• La dreapta, ajungând în sectorul (i,j+1) .
• Pe diagonala la dreapta în sus, ajungând în sectorul (i-1,j+1).
• Pe diagonala la dreapta în jos, ajungând în sectorul (i+1,j+1) .

Cerința

Sa se afișeze în câte moduri poate Carmen sa ajungă la Tulosba.

Date de intrare

Fișierul de intrare pitic.in conține pe prima linie numerele n și m cu semnificația din problema.

Date de ieșire

Fișierul de ieșire pitic.out va conține pe prima linie numărul S, reprezentând în câte moduri poate sa ajungă Carmen la Tulosba.

Restricții și precizări

• Carmen nu poate sa coboare sub nivelul 1
• Carmen nu poate sa urce mai sus de nivelul n pentru ca o sa fie spart de copii
• 1 ≤ n ≤ 43
• 1 ≤ m ≤ 43

Exemplu

pitic.in

3 3

pitic.out

2

pitic.in

7 1

pitic.out

1

pitic.in

4 4

pitic.out

4

Explicație

Exemplul 1 : Piticul Carmen poate sa meargă de 2 ori la dreapta sau o dată pe diagonala în sus la dreapta și odată pe diagonala în jos la dreapta.

Exemplul 2 : Piticul Carmen poate sa meargă doar la dreapta deoarece dacă urca pe nivelul 2 o sa ajungă în gradina.

Exemplul 3 :

• Modul 1: Dreapta de 3 ori
• Modul 2: Diagonala sus, Diagonala jos, Dreapta
• Modul 3: Diagonala sus, Dreapta , Diagonala jos
• Modul 4: Dreapta, Diagonala sus, Diagonala jos

#include <bits/stdc++.h>
using namespace std;

ifstream cin("pitic.in");
ofstream cout("pitic.out");

long long n , m , a[45][45];

int main()
{
    cin >> n >> m;
    a[1][1] = 1;
    for(int j = 1 ; j <= m ; j++)
        for(int i = 1 ; i <= n ; i++)
            a[i][j] += a[i + 1][j - 1] + a[i][j - 1] + a[i - 1][j - 1];

    cout << a[1][m];
}