[프로그래머스] 3xn 타일링

def solution(n):
    dp=[0]*(n+2)
    dp[2]=3
    for i in range(4,n+1,2):
        dp[i]+=(dp[i-2]*3)+2
        for j in range(2,i-2,2):
            dp[i]+=dp[j]*2
        dp[i]=dp[i]%1000000007
    return dp[n]
    
#0:0
#2:3=3
#4:11=9+2
#6:41=33+6+2
#8:153=123+22+6+2=dp[6]*3+dp[4]*2+dp[2]*2+2