깡총깡총

시간 제한1초메모리 제한128 MB

요약

1,2,3 크기의 도약을 내림차순으로 배열해 n을 표현하는 방법의 수를 1000000으로 나눈 나머지로 구합니다 (n은 최대 10^9).

난이도: 보통10점 중 5점
유형: 수학, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

CTP 마을에 사는 토끼 아람이는 한 번에 3미터, 2미터, 또는 1미터씩 뛰어서 총 n미터를 이동한다. 아람이가 이동해야 하는 거리 n이 주어졌을 때, 점프 길이가 증가하지 않는(즉, 바로 앞의 점프보다 뒤의 점프가 더 길어지지 않는) 순서로 이동하는 방법이 모두 몇 가지인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 이동해야 하는 거리 n이 주어진다. (1 ≤ n ≤ 10^9)

출력

이동하는 방법의 수를 1000000으로 나눈 나머지를 출력한다.

힌트

예를 들어 n = 6인 경우, 1, 2, 3을 더해서 6을 만들면서 점프 길이가 증가하지 않는 경우는 다음 7가지이다. 따라서 7을 1000000으로 나눈 나머지인 7을 출력한다.

3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1

예제6

예제 1
입력
```
6
```
예상 출력
```
7
```
예제 2
입력
```
1
```
예상 출력
```
1
```
예제 3
입력
```
2
```
예상 출력
```
2
```
예제 4
입력
```
3
```
예상 출력
```
3
```
예제 5
입력
```
5
```
예상 출력
```
5
```
예제 6
입력
```
7
```
예상 출력
```
8
```