2133.py

"""
dp[i] = 길이가 i일 때 3 * N 타일을 만들 수 있는 경우의 수

1. n이 홀수인 경우는 만들 수 없다.
2. n이 짝수인 경우는 몇 가지 경우를 생각해야 한다.
- n = 2일 때는 만들 수 있는 방법은 3가지이다.
- n = 4일 때는 만들 수 있는 방법은
n = 2일 때 만든 방법의 수 * n = 2를 만들었던 방법의 수 + n = 4를 만들어 내는 방법의 수
- 그렇다면 n = 6 일때는?

3. n = 4이상의 경우 각 n에 대하여 2개의 특수한 경우를 만들어 낼 수 있다.
4. dp는 결국 늘어나는 n에 대하여 바로 이전의 경우에 3가지 경우의 수를 곱하는 경우와
이전보다 더 먼 경우에 2가지 경우의 수를 곱하는 경우를 반복하여 더하면 우리가 원하는 답을 구할 수 있다.
5. 이 문제의 핵심은....각 단계에서 특수한 경우가 만들어 지는 것이다.
"""


n = int(input())

dp = [0 for i in range(n+1)]
dp[0] = 1
if n == 1:
    print(0)
else:
    dp[2] = 3
    for i in range(4, n+1):
        if (i % 2) != 0:
            continue
        for j in range(1, (i//2 + 1)):
            if j == 1:
                dp[i] += (dp[i-2*j] * 3)
            else:
                dp[i] += dp[i-2*j] * 2

    print(dp[n])