def numTilings(self, N: int) -> int:
# f(3) = 2 * f(2) + f(0) = 2 + f(0) = 1 -> f(0) = -1
# f(4) = 2 * f(3) + f(1) = 2 + f(1) = 2 -> f(1) = 0
# f(n) = f(n-1) + f(n-2) + 2 * T(n-1)
# 2 * T(n-1) = 2 * f(n-3) + 2 * T(n-2)
# f(n) = f(n-1) + 2 * f(n-3) + f(n-2) + 2T(n-2) = f(n-1) + f(n-3) + f(n-3) + f(n-2) + 2T(n-2) = f(n-1) + f(n-3) + f(n-1) = 2 * f(n-1) + f(n-3)
for i in range(3, N + 3):
dp[i] = 2 * dp[i-1] + dp[i-3]
return dp[-1] % (10 ** 9 + 7)