Shared code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const ll mod = 1e9 + 7;
 
void generateConfigurations (int mask, int cur_pos, int next_mask, int n, vector <int> &masks) {
    /*
	Variables mask and next_mask represent the current configuration of tiles
	and the next configuration of tiles for the grid (here, column of the original grid)
	of size n. variable cur_pos represents the current position within the grid. 

	(1) We check if cell already filled for the column
	(2) Whecks if we can place a vertical bar, foe which we have to move 2 cells ahead if yes
	(3) Place a horizontal bar
    */
    
    if (cur_pos == n) {
        masks.push_back(next_mask);
        return;
    }
 
    // (1)
    if ((mask >> cur_pos) & 1) {
        generateConfigurations(mask, cur_pos + 1, next_mask, n, masks);
        return;
    }
 
    // (2)
    if (cur_pos != (n - 1) && (mask >> (cur_pos + 1) & 1) == 0) {
        generateConfigurations(mask, cur_pos + 2, next_mask, n, masks);
    }
 
    // (3)
    generateConfigurations(mask, cur_pos + 1, next_mask | (1 << cur_pos), n, masks);
}
 
ll WaysToTileConfig (vector <vector <int>> &ways, int n, int m, int mask, int column_num) {
	/*
	(1) We check Checks if column is the last column of the grid, and if yes, return 1
		if the entire grid is tiled, else return 0
	(2) If the number of ways of ways to tile the current configuration has already been
		calculated, returns the same
	(3) Generates all possible next configurations from current configuration 
	(4) Now we iterate over all possible next configurations and then we recursively call 
		WaysToTileConfig() function to get number of possible ways to tile the grid for the corresponding
		configuration
	*/
 
 
 
    // (1)
    if (column_num == m) return (mask == 0); 
 
    // (2)
    if (ways[mask][column_num] != -1) return ways[mask][column_num];
 
    vector <int> masks;
 
    // (3)
    generateConfigurations(mask, 0, 0, n, masks);
 
    ll ans = 0;
 
    // (4)
    for (auto &next_mask : masks) {
        ans += WaysToTileConfig(ways, n, m, next_mask, column_num + 1);
        ans %= mod;
    }
    return (ways[mask][column_num] = ans);
}
 
int main() {
    int n, m; cin >> n >> m;
 
    vector <vector <int>> ways (1 << (n + 1), vector (m, -1));
    cout << WaysToTileConfig(ways, n, m, 0, 0);
 
    return 0;
}