Informatica Online Judge

  이진수 카드 [1054 / 041E]

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


The Champion of this Problem (C++) : gs19022 - 0ms / 211byte
My Best Submission (C++) : N/A

[koistudy.net (unknown)]

Background

경곽이에게 2진 수열을 가르쳐 주기 위해, 경곽이 정보선생님은 경곽이에게 숫자카드를 선물해주셨다.

선물 받은 카드는 2가지 종류로 구성되어 있다.

2가지 값은 각각 "00" 또는 "1"이 쓰여 있는 카드들이다.

따라서 경곽이는 주어진 카드로는 N개 수열로 이루어진 모든 2진 수열을 만들 수 없다는 사실을 알았다.

예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없다.)

또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.

우리는 N이 주어졌을 때 경곽이가 만들 수 있는 모든 가짓수를 구할 수 있는 프로그램을 작성하시오.
(단, 각 카드는 무한이 많은 것으로 가정한다.)

Input

첫 번째 줄에 자연수 N이 주어진다.

[입력값의 정의역]
100,000 <= N <= 1,000,000

[Sub-Task Info]
#1 ~ #10 : 추가제한조건은 없다.

Output

첫 번째 줄에 경곽이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.

IO Example

입력
4

출력
5

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