Informatica Online Judge

  코드업 블럭채우기 5 [1657 / 0679]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 99   Total Tried : 103


The Champion of this Problem (C++) : histeria - ms / 294byte
My Best Submission (C++) : N/A

[CODEUP]

Background

$3×1×1$ 블럭과 $3×2×1$ 블럭을 이용해서 $3×n×1$ 블럭 판을 맞추려고 한다.

가능한 모든 가짓수를 $1,000$으로 나눈 나머지를 구해보자.

Input

첫 줄에 $n$이 입력된다.

[입력값의 정의역]

$1 \leq n \leq 100,000$

Output

$3×n×1$의 블럭 판을 채울 수 있는 방법의 수에 $1,000$로 나눈 나머지를 출력하시오.

IO Example

입력
331

출력
602

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]