看到这道题很明显的知道纵向递推是不可取的，所以很自然的想到横向递推。
由于只有存在四个人，可以想到枚举每个人取的状态，用状态压缩去转移。空间只需要取5000图片说明16就行了
每次都把上一种棋子取的情况转移过来，能多转移的情况当且仅有此时的状态和上一次的状态当且只有一个位置不同，并且当前状态不同的位置为1并且能取上一次状态为0。
时间复杂度O(5000 * 16 * 16)

#include <bits stdc++.h>

#define ll long long
#define int long long
#define pii pair<int, int>
using namespace std;
const int maxn = 1e6+10;
const ll inf = 1e18;

template <typename _tp>
inline void read(_tp& x) {
    char ch = getchar(), sgn = 0;
    while (ch ^ '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') ch = getchar(), sgn = 1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if (sgn) x = -x;
}

int f[5200][20];
string s[4];

bool judge(int x, int y, int u){
    int a = __builtin_popcount(x);
    int b = __builtin_popcount(y);
    if(a == b) return false;
    else if(a - b == 1){
        int pos = -1;
        int num = 0;
        for(int i = 0; i < 4; ++i){
            int c = ((x>>i)&1), d = ((y>>i)&1);
            if(!c && d) return false;
            if(c && !d) pos = i, num++;
        }
        if(s[pos][u] == '0' || num != 1) return false;
        //cout << x << " " << y << endl;
        return true;
    }
    return false;
}
signed main(){
    int n;
    read(n);
    s[0] += "#";
    s[1] += "#";
    s[2] += "#";
    s[3] += "#";
    for(int i = 0; i < 4; ++i){
        string t;
        cin >> t;
        s[i] += t;
    }
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < (1<<4); ++j) f[i][j] = f[i-1][j];
        for(int j = 1; j < (1<<4); ++j){
            for(int k = 0; k < (1<<4); ++k){
                if(judge(j, k, i) == false) continue;
                else {
                    f[i][j] = f[i][j] + f[i-1][k];
                }
            }
        }
    }
    printf("%lld", f[n][(1<<4)-1]);
    //return 0;
}