Cerinţa

Harta jocului PacmMan este sub forma unui dreptunghi împărțit în camere organizate pe linii și coloane. Din fiecare cameră se poate merge în camera situate pe coloana următoare și pe aceeași linie, sau in camera de pe coloana următoare și linia următoare, dar fără a ieși din hartă. Astfel din camera (i,j) se poate merge în camerele (i,j+1) și (i+1,j+1). PacMan se află în camera situată pe prima linie și pe prima coloana (1,1) și trebuie să ajungă în camera de pe ultima linie și ultima coloană (n,m). Calculați și afișați numărul de trasee pe care poate PacMan să parcurgă harta.

Date de intrare

Fișierul de intrare pacman_xi.in conține pe prima linie merele n și m, reprezentând numărul de linii și, respectiv, de coloane ale hărții.

Date de ieșire

Fișierul de ieșire pacman_xi.out va conține pe prima linie numărul s, reprezentând numărul de trasee pe care poate PacMan să parcurgă harta.

Restricții și precizări

• 1 ≤ n,m ≤ 40

Exemplu

pacman_xi.in

3 4

pacman_xi.out

3

Explicație

Cele 3 trasee sunt cele din imaginea de mai jos.

#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{

    cin>>n>>m;
    a[1][1]=1;

    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)
            a[i][j] = a[i-1][j-1]+a[i][j-1];

    cout<<a[n][m]<<endl;
    return 0;
}