def solution(n):
    """
    [프로그래머스] 3 x N 타일링
    
    1. 기본 규칙 (Base Case)
       - 세로가 3이므로 전체 칸 수는 3 * N입니다. 타일은 항상 2칸씩 차지하므로, 
         가로 길이(N)가 홀수이면 전체 칸 수가 홀수가 되어 완벽히 채울 수 없습니다.
         -> f(홀수) = 0
       - N = 2 일 때, 기본 채우기 경우의 수는 3가지입니다.
         -> f(2) = 3
       
    2. 점화식 유도 원리 (핵심 메커니즘)
       타일링을 중복 없이 세는 대원칙은 "맨 처음으로 세로 분할선(잘리는 선)이 어디서 나타나는가?"입니다.
       
       (1) f(n-2) * 3  : 맨 처음 2칸째에서 분할선이 생기는 경우
           - 앞의 2칸을 일반 패턴(3가지)으로 채우고, 나머지 n-2칸을 자유롭게 채웁니다.
           
       (2) 2 * f(n-4)  : 앞의 2칸에서는 안 잘리고, '정확히 4칸째'에서 처음 분할선이 생기는 경우
           - 앞의 4칸이 중간에 절대 쪼개지지 않는 고유한 '길이 4짜리 특수 패턴'이어야 합니다.
           - 이 특수 패턴은 뒤집은 모양까지 딱 2가지만 존재합니다.
           
           ※ 길이 4짜리 고유 특수 패턴 예시 (같은 알파벳은 하나의 타일)
             [ 1번 형태 ]          [ 2번 형태 (상하반전) ]
             A  A  B  B            C  F  F  E
             C  D  D  E            C  D  D  E
             C  F  F  E            A  A  B  B
             
             => 보시다시피 2열 뒤(중간)를 세로로 칼질하려 하면 D와 F 타일에 걸려 자를 수 없습니다.
                정확히 4열째에 도달해야만 위아래가 탁 트인 세로 분할선이 나타납니다.
                이런 통짜 덩어리 뒤에 남은 n-4칸을 채우므로 2 * f(n-4)가 됩니다.
                
       (3) 2 * f(n-6)  : 앞의 2칸, 4칸에서는 안 잘리고, '정확히 6칸째'에서 처음 분할선이 생기는 경우
           - 마찬가지로 중간에 절대 안 잘리는 '길이 6짜리 통짜 특수 패턴(2가지)' 뒤에 n-6칸을 채웁니다.
           
       (4) ... 이 조건이 8, 10, ... n칸까지 쭉 누적됩니다.
           - 마지막에 f(0) 공간이 남는 것은 'n칸 전체가 하나의 거대한 특수 패턴'인 경우를 뜻합니다.
           - 계산 편의를 위해 아무것도 없는 빈 공간을 채우는 경우의 수 f(0) = 1로 설정합니다.
         
    3. 최종 점화식 (수학적 표현)
       f(n) = f(n-2) * 3 + 2 * (f(n-4) + f(n-6) + f(n-8) + ... + f(0))
    """
    
    # N이 홀수이면 타일을 빈틈없이 채울 수 없음
    if n % 2 != 0:
        return 0

    MOD = 1_000_000_007
    
    # DP 테이블 초기화 (인덱스 n까지 접근해야 하므로 n+1 크기)
    dp = [0] * (n + 1)
    dp[0] = 1  # n칸 전체가 통짜 특수 패턴일 때(2 * f(0))를 처리하기 위한 베이스 값
    dp[2] = 3

    # 가로 길이 4부터 n까지 2씩 증가하며 DP 테이블 채우기
    for i in range(4, n + 1, 2):
        # 1. 기본 패턴 (바로 직전 단계에서 가장 바깥쪽 2칸을 확장하는 경우)
        dp[i] = dp[i - 2] * 3
        
        # 2. 누적되는 고유 특수 패턴들 적용 (4칸, 6칸, 8칸... 단위로 처음 쪼개지는 경우)
        for j in range(i - 4, -1, -2):
            dp[i] += dp[j] * 2
            
        # 프로그래머스 조건: 값이 커질 수 있으므로 계산 중간에 계속 1,000,000,007로 나머지 연산
        dp[i] %= MOD

    return dp[n]