int count_tilings ( int N,int M ) {
    int count = 1;
    int i, j;

    for (i=0; i<=M-2; i++)
    {
        for (j=0; j<=N-2; j++)
        {
            count ++;
            count += count_tilings(N-j-2, M) - 1;
            count += count_tilings(N, M-i-2) - 1;
            count -= count_tilings(N-j-2, M-i-2) - 1;
        }
    }

    return count;
}