public class Solution {
    public int NumTilings(int n) {

        if(n == 1) return 1;

        int[] f = new int[n+1];
        int[] l = new int[n+1];
        int[] u = new int[n+1];

        f[1]=1;
        f[2]=2;
        l[1]=0;
        l[2]=1;

        u[1]=0;
        u[2]=1;

        int M = 1000000007;
        for(int index = 3; index <= n; index++)
        {
            f[index] = ((f[index-1] + f[index-2]) % M + (l[index-1] + u[index-1]) % M) % M;
            l[index] = (f[index-2] + u[index-1]) % M;
            u[index] = (f[index-2] + l[index-1]) % M;
        }


        return f[n];
    }
}