#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
using namespace std;

int fib(int n) {
    if (n<=1) return n;
    return fib(n-1)+fib(n-2);
}

int memo[10000];

int fib2(int n) {
    if (n<=1) return n;
    if (memo[n]>0) return memo[n];
    int r=fib2(n-1)+fib2(n-2);
    memo[n]=r;
    return r;
}

void fibonacci() {
    for (int n=0;n<=10;n++) {
        cout << n << ": " << fib(n) << endl;
    }
    //cout << fib(50) << endl;
    cout << fib2(10) << endl;
    cout << fib2(1000) << endl;
}

int main() {
    vector<string> lab = {
        ".#....",
        "....#.",
        ".#..#.",
        "......"
    };
    int f[10][10];
    memset(f,0,sizeof(f));
    int n=lab.size(), m=lab[0].size();
    for (int i=n-1;i>=0;i--) {
        for (int j=m-1;j>=0;j--) {
            if (i==n-1 && j==m-1) f[i][j]=1;
            else if (lab[i][j]=='#') f[i][j]=0;
            else f[i][j]=f[i+1][j]+f[i][j+1];
        }
    }
    cout << f[0][0] << endl;
    return 0;
}