# Appreciation

/*
 * Problem :: 1720 / 타일 코드
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 서로 좌우 대칭을 이루는 중복된 표현을 서로 다른 경우로 처리하는 경우
 *   dp1[i] = dp1[i-1] + 2*dp1[i-2]
 *   + 블럭들을 다음과 같이 표현하자
 *     |   --   ㅁㅁ
 *     |   1x2  ㅁㅁ
 *    2x1       2x2
 *    # dp1[3] 의 경우
 *      |||  --|  |--  ㅁㅁ|  |ㅁㅁ
 *      |||  --|  |--  ㅁㅁ|  |ㅁㅁ
 *      이렇게 5가지 경우가 있다
 *      -> 이는 서로 좌우 대칭을 이루는 표현을 중복되지 않게 센 것이다
 *         만약 중복된 표현을 같은 경우로 처리한다면
 *         |||  --|  ㅁㅁ|
 *         |||  --|  ㅁㅁ|
 *         이렇게 3가지 경우가 있다
 *
 * - 서로 좌우 대칭을 이루는 표현을 같은 경우로 처리했을 때
 *   dp1[i] = (그 자체로 좌우 대칭인 경우의 수) + 2*(그 자체로 좌우 대칭이 아닌 경우의 수)
 *   임을 알 수 있다
 *   + 서로 좌우 대칭을 이루는 표현을 서로 다른 경우로 처리했을 때는
 *     dp1[i] = (그 자체로 좌우 대칭인 경우의 수) + (그 자체로 좌우 대칭이 아닌 경우의 수)
 *     이므로 맥락을 주의하자
 *   + 우리가 구하고자 하는 값은
 *     서로 좌우 대칭을 이루는 표현을 같은 경우로 처리했을 때
 *     (그 자체로 좌우 대칭인 경우의 수) + (그 자체로 좌우 대칭이 아닌 경우의 수)
 *     이다
 *     # 미지수가 2개인 연립방정식의 관점으로 바라보면
 *       x(i) = 2xi 판에서 그 자체로 좌우 대칭인 경우의 수
 *       y(i) = 2xi 판에서 그 자체로 좌우 대칭이 아닌 경우의 수
 *       라고 할 때
 *       dp1[i] = x(i) + 2y(i) 이며
 *       구하고자 x(i) + y(i) 의 값을 구하기 위해서는
 *       x(i) 나 y(i) 의 값을 알아내거나
 *       관련된 새로운 방정식을 찾아야 한다
 *
 * - y(i) 를 구해보자
 *   + i=4 일 때
 *     dp1[2]*dp1[2] + dp1[1]*dp1[3] + ...
 *     근데 dp1[2]*dp1[2] 와 dp1[1]*dp1[3] 에 겹치는 경우가 있는데?
 *     || ||   | |||
 *     || ||   | |||
 *     2  2    1 3
 *     같은 경우인데 2번 세게 되네?
 *     # 마땅한 방법이 떠오르지 않는다
 *       y(i) 를 구하는 건 조금 무리인것 같다...
 *
 * - x(i) 를 구해보자 <= 그 자체로 대칭인 경우의 수 구하는 건 좀 쉽지 않을까?
 *   + i=4 일 때
 *     2x4 판을 둘로 나눈 뒤 왼쪽에 있는 판을 채우는 경우의 수 : dp1[2]
 *     가운데 2x1 타일 2개 넣어두고 나머지 판을 둘로 나눈 뒤
 *     왼쪽에 있는 판을 채우는 경우의 수 : dp1[1]
 *     가운데 2x2 타일 1개 넣어두고 나머지 판을 둘로 나눈 뒤
 *     왼쪽에 있는 판을 채우는 경우의 수 : dp1[1]
 *     # 즉, i 가 짝수일 때 그 자체로 대칭인 경우는 다음과 같은 3개의 꼴이 가능하다
 *       ...  ...
 *       ...  ... => dp1[i/2]
 *
 *       ...--...
 *       ...--... => dp1[(i-2)/2]
 *
 *       ...ㅁㅁ...
 *       ...ㅁㅁ... => dp1[(i-2)/2]
 *   + i=5 일 때
 *     가운데 2x1 타일 1개 넣어두고 나머지 판을 둘로 나눈 뒤
 *     왼쪽에 있는 판을 채우는 경우의 수 : dp1[2]
 *     # 즉, i 가 홀수일 때 그 자체로 대칭인 경우는
 *       ...|...
 *       ...|... => dp1[(i-1)/2]
 *
 * - dp1[i] = x(i) + 2*y(i)
 *   dp2[i] = x(i)
 *   x(i) + y(i) = (dp1[i] + dp2[i]) / 2
 *
 * Point
 * - 개인적으로 DP 문제중 가장 어려웠던 문제중 하나이다...
 *   + 항상 DP 문제의 경우
 *     점화식을 구한 후 dp 배열 하나만으로 풀리는 문제가 다인 줄 알았는데...
 *     배열을 두개나 사용하는 문제를 처음 풀어봤다
 *     # 사실 배열을 하나만 사용해야된다는 그런 제한은 어디에도 없는 데 말이다...
 *       역시 알고리즘 문제는 항상 짜릿해, 늘 새로워, (잘 생긴게 최고야?!?!)
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;

    // Process
    /* 서로 좌우 대칭을 이루는 표현을 같은 경우로 처리했을 때
     * dp1[i] = 2*i 판을 타일로 채우는 경우의 수
     *        = (그 자체로 좌우 대칭인 경우의 수)
     *          + 2*(그 자체로 좌우 대칭이 아닌 경우의 수) */
    int dp1[N+1];
    memset(dp1, 0, sizeof(dp1));
    dp1[0] = dp1[1] = 1;
    for (int i=2; i<=N; i++) {
        dp1[i] = dp1[i-1] + 2*dp1[i-2];
    }

    /* dp2[i] = 2xi 판을 타일로 채우되 타일의 모양이 그 자체로 좌우 대칭인 경우의 수 */
    int dp2[N+1];
    memset(dp2, 0, sizeof(dp2));
    for (int i=1; i<=N; i+=2) { /* 판의 길이가 홀수인 경우 */
        /* 가운데 2x1 타일을 넣은 경우 */
        dp2[i] = dp1[(i-1)/2];
    }
    for (int i=2; i<=N; i+=2) { /* 판의 길이가 짝수인 경우 */
        /* 가운데 타일을 넣지 않은 경우, 2x1 타일 2개를 넣은 경우, 2x2 타일 1개를 넣은 경우 */
        dp2[i] = dp1[i/2] + 2*dp1[(i-2)/2];
    }

    /* dp1[i] = x(i) + 2*y(i)
     * dp2[i] = x(i)
     * x(i) + y(i) = (dp1[i] + dp2[i]) / 2 */
    int ans = (dp1[N] + dp2[N]) / 2;

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */