790

class Solution {
public:
    int numTilings(int n) {
        vector<long long int> dp1(4), dp2(4);
        dp1[0] = 1;

        int mod = int(1e9)+7;
        for(int i=0; i<n; i++){
            dp2[0] = (dp1[0]+dp1[3])%mod;
            dp2[1] = (dp1[0]+dp1[2])%mod;
            dp2[2] = (dp1[1]+dp1[0])%mod;
            dp2[3] = (dp1[1]+dp1[2]+dp1[0])%mod;
            dp1 = dp2;
        }
        return dp2[0];
    }
};