Informatica Online Judge

  숲속의 나무들 [1317 / 0525]

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


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

[Beaver 2013 modified]

Background

떤 숲에는 A형, B형 2가지 형태의 나무들이 있다.

A형 나무들은 수명이 1년인데, 1년 뒤에는 B형 나무로 바뀐다.

B형 나무들은 죽지 않고 영원히 사는데 매년 말에 A형 나무를 새로 만들어낸다.

아래의 그림은 A형 나무와 B형 나무가 1년 뒤에 변하는 형태를 보여주는 것이다.







예를 들어, A형 나무 한 그루로 시작하면, 1년 뒤에는 B형 나무 한 그루만 남게 되고, B형 나무 한 그루로 시작하면, 1년 뒤에는 A형 나무 한 그루와 B형 나무 한 그루가 남게 된다.

만약 A형 나무 한 그루로 시작해서 숲이 만들어지기 시작한다면, n년 뒤에 A형 나무의 개수와 B형 나무의 개수는 각각 몇 그루씩 될까?

이를 해결할 수 있는 프로그램을 작성하시오.

Input

첫 줄에 n이 입력된다.

[입력값의 정의역]
0 <= n <= 5,000

Output

첫 줄에 A형 나무와 B형 나무가 몇 그루인지 공백을 두고 출력한다.

단, 값이 너무 커지기 때문에 10억 7(1e9 + 7)로 나눈 나머지 값을 출력한다.

IO Example

입력
3

출력
1 2

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