Shared code

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9+7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;

    matrix<int> valid(1<<n);

    // checks for every pair of masks if they are compatible
    for(int i = 0; i < (1<<n); i++){
        int x = (~i) &((1<<n)-1);
        // iterating over submasks is sufficient and reduces the complexity from 4^n to 3^n
        for(int j = x; j; j = (j-1)&x){ 
            int innactive = (~i)&(~j); // here a bit is on iff its inactive in both i and j
            int last = -1; //last = least significant bit of the current segment of bits that are innactive in both i and j
            // last = -1 is a code for not being on a segment of that sort 
            bool ok = 1;
            for(int k = 0; k < n; k++){
                if((1<<k)&innactive){
                    if(last == -1) // we enter a segment
                        last = k;
                } else {
                    if(last != -1){ // we leave a segment
                        ok&=(k-last)%2 == 0;
                        last = -1;
                    }
                }
            }
            if(last!=-1)
                ok&=(n-last)%2 == 0;
            
            if(ok)
                valid[i].push_back(j); // i and j are compatible, so we push it into the vector
        }

        // Since 0 is not included in our loop, i had to copy paste this. Sorry for this ugly solution!
        {
            int j = 0;
            int innactive = (~i)&(~j); // here a bit is on iff its inactive in both i and j
            int last = -1; //last = least significant bit of the current segment of bits that are innactive in both i and j
            // last = -1 is a code for not being on a segment of that sort 
            bool ok = 1;
            for(int k = 0; k < n; k++){
                if((1<<k)&innactive){
                    if(last == -1) // we enter a segment
                        last = k;
                } else {
                    if(last != -1){ // we leave a segment
                        ok&=(k-last)%2 == 0;
                        last = -1;
                    }
                }
            }
            if(last!=-1)
                ok&=(n-last)%2 == 0;
            
            if(ok)
                valid[i].push_back(j); // i and j are compatible, so we push it into the vector
        }
    }


    matrix<ll> dp(m+2,vector<ll>(1<<n));

    dp[1][0] = 1; // innitially theres nothing poking into column 1

    for(int i = 2; i <= m+1; i++){
        for(int mask = 0; mask < (1<<n); mask++){
            for(int k : valid[mask]) // iterating over the masks that are compatible with "mask"
                dp[i][mask]+=dp[i-1][k];

            dp[i][mask]%=MOD;
        }
    }
    cout << dp[m+1][0] << '\n';

    
    return 0;

}