dp[i][1] = 2*dp[i-1][1] + dp[i-1][0]
dp[i][0]=  dp[i-1][1] + 4*(dp[i-1][0])


dp[i][1] = 2*dp[i-1][1] +dp[i-1][0]
=>2*ways because we can either extend the current level to one level down or keep another new tile + 1*ways because we can only keep another new tile and cannot extend the current level downwards
dp[i][0] = dp[i-1][1]+ 4*dp[i-1][0]
=>1*ways because we can only keep another new set of tiles and cannot extend the current level + 4*ways because we can either keep a new tile, or extend both the sides together or extend a single side at one time(left or right side, so intotal 4 ways

#include<bits/stdc++.h>
using namespace std;

#define f(i,a,b)  for(int i=a;i<b;i++)
#define modm 	  1000000007
#define ll        long long
const int N=1000005;
ll dp[N][2];
int main(){
	dp[1][0]=1;
	dp[1][1]=1;
	for(int i=2;i<=N;i++){
		dp[i][1]=(2*(dp[i-1][1]%modm))%modm + (dp[i-1][0]%modm);
		dp[i][0]=(dp[i-1][1]%modm)+(4*(dp[i-1][0]%modm))%modm;
	}
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		cout<<(dp[n][0]%modm+dp[n][1]%modm)%modm<<"\n";
	}
	return(0);
}

#include<bits/stdc++.h>
using namespace std;

#define pii         pair<int,int>
#define ff          first
#define ss          second

int32_t main(){

    ios_base::sync_with_stdio(0);cin.tie(0);
    cout.tie(0);
   
    int n,x;cin>>n>>x;
    vector<int> w(n);
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    vector<pii> dp(1<<n);
    dp[0]={1,0};    
    for(int mask=1;mask<(1<<n);mask++){
        //to store the best result for a particular mask. Best result means less number of rides 
        pii bestResult={INT_MAX,INT_MAX};
        for(int j=0;j<n;j++){
            if(mask &(1<<j)){
                auto res = dp[mask^(1<<j)];
                //the jth person can be accommodated in the last ride, we have used, so number of rides remain same
                if(res.ss + w[j] <=x  ){
                    res={res.ff,res.ss+w[j]};
                }
                //the jth person need another new ride
                else{
                    res = {res.ff+1, w[j]};
                }
                bestResult=min(bestResult,res);
            }   
        }
        dp[mask] =bestResult;
    }
    cout<< dp[(1<<n)-1].ff<<"\n";
    return(0);
}

#include<bits/stdc++.h>
using namespace std;

#define f(i,a,b)        for(int i=a;i<b;i++)
#define int             long long

int dp[20][10][2][2];
// finding number of numbers having no adjancent digit from 0 to n
int solve(string& num,int n,int prev_dig,int i,bool leading_zeroes,int tight){
    if(i==n){
        return(1);
    }
    if(prev_dig!=-1 and dp[i][prev_dig][leading_zeroes][tight]!=-1){
        return(dp[i][prev_dig][leading_zeroes][tight]);
    }
    // bounds for the ith digit - possible values for the ith digit
    int lb = 0;
    int ub = (tight==1)?(num[i]-'0'):9;
    int ans=0;
    f(dig,lb,ub+1){
        //case of similar adjancent digits
        if(dig==prev_dig and dig!=0){continue;}
        // case when '00' occurs in the number (but not at the start(seen from left side))
        if(dig==prev_dig and dig==0 and leading_zeroes==0){continue;}
        ans+= solve(num,n,dig,i+1,leading_zeroes&dig==0 ,tight&(dig==ub));
    }
    return(dp[i][prev_dig][leading_zeroes][tight]= ans);
}
bool check(string a){
    int ns=a.size();
    bool flag=true;
    f(i,1,ns){
        if(a[i-1]==a[i]){flag=false;}
    }
    return(flag);
}
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cout.tie(0);
    string a,b;
    cin>>a>>b;
    int na=a.size();
    int nb=b.size();
    memset(dp,-1,sizeof(dp));
    int ans= solve(b,nb,-1,0,1,1);
    memset(dp,-1,sizeof(dp));
    ans -= solve(a,na,-1,0,1,1); 
    ans+= check(a)?1:0;
    cout<<ans<<"\n";      
    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define f(i,a,b)        for(int i=a;i<b;i++)
#define int             long long 
#define modm            1000000007
#define vi              vector<int>
#define pb              push_back

int n,m;
int dp[1005][(1<<12)];

//generating all possible mask- representing all possible states given the current mask
//here i represents the row
void generate_next_masks(int current_mask,int i,int next_mask, vi& container){
  
    if(i==(n+1)){
        container.pb(next_mask);
        return;
    }
    if(current_mask&(1<<i)){
        generate_next_masks(current_mask,i+1,next_mask,container);
    }
    if(i!=n){
        
        if(((current_mask & (1<<i))==0) and ((current_mask&(1<<(i+1))) ==0)  ){
            generate_next_masks(current_mask,i+2,next_mask,container);
        }
    }
 
    if((current_mask&(1<<i))==0){
        generate_next_masks(current_mask, i+1 , next_mask+(1<<i) , container);
    }
}
 
int solve(int col,int mask){
  
    if(col == (m+1)){
        //checking that no block flows out of the board at the last column. That's there is not block of size 1x2 in the ith column 
        if(mask==0){
            return(1);
        }
        return(0);
    }
 
    if(dp[col][mask]!= -1){return(dp[col][mask]);}
    int ans=0;
    vi next_masks;
    generate_next_masks(mask,1,0,next_masks);
 
    //trying with all possible mask for the current column 
    for(auto maskk : next_masks){
        ans = (ans%modm + solve(col+1,maskk)%modm)%modm;
    }
    next_masks.clear();
    return(dp[col][mask]=ans%modm);
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    cout<<solve(1,0)<<"\n";
    return 0;
}