Expert.
Put your skills to the test.

Problem summary

Count tilings of a 2×N strip using rotatable 2×1 dominoes (type I), L trominoes (a 2×2 square missing one cell), or both, depending on T. Output modulo 1000000007.

Constraints

1 ≤ N ≤ 10^18; 1 ≤ T ≤ 3.

Worked example

Official example, transcribed with whitespace restored from the PDF.

4 3

11

Solution analysis

1. Sweep columns, remembering the two cells already occupied by tiles extending from the preceding column. There are only four frontier masks. To construct a transition, fill the first uncovered cell of the current column with each allowed tile orientation that covers it and does not overlap any occupied cell.
2. All tiles fit inside two consecutive columns. Encode their four cells by bits 0,1 for the current column and 2,3 for the next. Domino masks are 3,5,10; L masks are 7,11,13,14. Once the current mask is full, record the next-column mask as the transition endpoint.
3. This produces a 4×4 transfer matrix. Its Nth power maps the initially empty frontier to the frontier after N columns; entry [0][0] counts complete tilings. For N=4 and both types, that entry is 11. Binary exponentiation handles N up to 10^18.

Why it works

At each recursive step the first uncovered cell belongs to exactly one tile in any complete extension, and the enumerated masks are exactly its possible placements. Thus each extension is generated once. Frontier masks contain all information about overlap across the boundary. Matrix multiplication concatenates independently valid column transitions, so the Nth power counts precisely all tilings; requiring final mask zero excludes protrusions.

Watch out. Count all four L orientations, permit rotations, and require an empty final frontier.

An independently written complete program with standard headers.

// Key idea: At each recursive step the first uncovered cell belongs to exactly one tile in any
// complete extension, and the enumerated masks are exactly its possible placements. Thus each
// extension is generated once.
#include<array>
#include<functional>
#include<iostream>
#include<vector>
using namespace std;
const long long MOD=1000000007;
using Matrix=array<array<long long,4>,4>;
Matrix multiply(const Matrix&a,const Matrix&b){
    Matrix c{};
    for(int i=0;i<4;++i){
        for(int k=0;k<4;++k){
            for(int j=0;j<4;++j){
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    return c;
}
int main(){
    unsigned long long n;
    int type;
    cin>>n>>type;
    vector<int>tiles;
    if(type!=2){
        tiles={3,5,10};
    }
    if(type!=1){
        for(int mask:{7,11,13,14}){
            tiles.push_back(mask);
        }
    }
    Matrix transition{},result{};
    for(int start=0;start<4;++start){
        function<void(int)>fill=[&](int mask){
            if((mask&3)==3){
                ++transition[start][mask>>2];
                return;
            }
            int bit=(mask&1)?2:1;
            for(int tile:tiles){
                if((tile&bit)&&!(tile&mask)){
                    fill(mask|tile);
                }
            }
        };
        fill(start);
        result[start][start]=1;
    }
    while(n!=0){
        if(n&1){
            result=multiply(result,transition);
        }
        transition=multiply(transition,transition);
        n>>=1;
    }
    cout<<result[0][0]<<'\n';
}