Shared code

//https://usaco.guide/adv/dp-more?lang=cpp
#include<bits/stdc++.h>
using namespace std;
class CountingTilings{
int n,m;
using ll=long long int;
ll mod=1e9+7;
vector<vector<ll>>tilingWays;
public:
  CountingTilings(int n,int m){
    this->n=n;
    this->m=m;
    tilingWays.resize(m+1,vector<ll>(1<<n,0));
    tilingWays[0][0]=1; //only vertical tiles are there initially so only one way 
  }
  //Find all valid tiles arrangement if tiling way for the previous column is given
  // 1 is for horizontal tile and 0 is for vertical tile.
void generateTilings(int prevTiling,int i,vector<int> &Tilings,int tiling){  
  if(i==n){
    Tilings.push_back(tiling);
    return;
   }
   if((1<<i)&prevTiling){
     generateTilings(prevTiling,i+1,Tilings,tiling);
   }else{
    generateTilings(prevTiling,i+1,Tilings,tiling|(1<<i));
    if((i+1<n) and ((1<<(i+1)) & prevTiling)==0){
      generateTilings(prevTiling,i+2,Tilings,tiling);
    }
   } 
  }
  ll getCountTilings(){
  //There are maximum 1024 tiling arrangements for particular column when n=10
  //1 represents horizontal tiling and 0 is for vertical tiling.
  //Thinking brute force way , first total number of ways to tile first column is determined then 2nd column and so on.
  // last column cannot contain horizontal tile so tilingWays[m][0] is the solution where 0 is no horizontal tile.
  ll maxTilings=1<<n;
  for(int col=1;col<=m;col++){
    for(int previousTiling=0;previousTiling<maxTilings;previousTiling++){
        //Here it is decided for tiling from previous column , how many valid tiling ways can be generated.   
       //if previous column has horizontal tile then that column's row cannot be tiled. 
      if(tilingWays[col-1][previousTiling]){
        vector<int> Tilings;
        generateTilings(previousTiling,0,Tilings,0);
        for(int newTiling:Tilings){
           tilingWays[col][newTiling]=(tilingWays[col][newTiling]+tilingWays[col-1][previousTiling])%mod;
        }
      }
    }
  }
  return tilingWays[m][0];
 }
};
 
int main() {
  int n,m;
  cin>>n>>m;
  CountingTilings cnt(n,m);
  cout<<cnt.getCountTilings()<<endl;
}