시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB114237331834.230%

문제

떡파이어의 불로장생의 비밀은 바로 떡국이다.

떡파이어는 떡국을 먹은 그릇의 개수만큼 나이를 먹는다. 그들은 매일 떡국을 먹는데, 떡국을 먹는대로 바로 소화가 가능하기 때문에 하루에 얼마든지 원하는만큼 떡국을 먹을 수 있다. 그러나 전에 떡국을 얼마나 먹었든지, 그들은 기구하게도 떡국을 하루라도 먹지 않으면 생을 마감하게 된다.

어느 날, 디디는 어떤 떡파이어가 N세로 생을 마감하기까지 어떤 생을 살아왔는지 알고 싶어서, 그의 나이를 먹는 과정의 경우의 수를 세려고 한다. 그렇지만, 떡파이어의 나이가 많을 수록 그 경우의 수는 무수히 많아지기 때문에 디디는 곤란해하고 있다.

그런 디디를 위해 N세로 생을 마감한 떡파이어가 나이를 먹는 과정의 경우의 수를 세는 프로그램을 작성해야 한다.

떡파이어의 나이는 0세부터 시작된다.

N이 3일때를 예로 들면,

  • 첫째 날 3개, 둘째 날 0개
  • 첫째 날 1개, 둘째 날 2개, 셋째 날 0개
  • 첫째 날 2개, 둘째 날 1개, 셋째 날 0개
  • 첫째 날 1개, 둘째 날 1개, 셋째 날 1개, 넷째 날 0개로

총 경우의 수는 4이다.

입력

정수 N이 주어진다. (0 ≤ N ≤ 1012)

출력

나이를 먹는 방법의 가짓 수를 109 + 7로 나눈 나머지를 출력하시오.

예제 입력 1

3

예제 출력 1

4

출처

Contest > BOJ User Contest > 네블컵 > 제1회 네블컵 K번