Counting Tilling

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
const int M = 1111;
const int N = 11;

ll dp[N][M][1 << N];
int n ,m;

ll calc(int i ,int j ,int mask)
{
    if( i == n ) return calc(0 ,j + 1 ,mask);
    if( j == m ) return !mask;

    ll &re = dp[i][j][mask];
    if( re + 1 ) return re;

    re = calc(i + 1 ,j ,mask ^ (1 << i));
    re %= MOD;

    int T = mask & (1 << i);
    if( T == 0 && i <= n - 2 )
    {
        T = mask & (1 << (i + 1));
        if( T == 0 )
        {
            re += calc(i + 2 ,j ,mask);
            re %= MOD;
        }
    }

    return re;
}

int main()
{
    scanf("%d%d" ,&n ,&m);

    memset(dp ,-1 ,sizeof dp);

    printf("%lld" ,calc(0 ,0 ,0));

    return 0;
}