깡총깡총

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

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

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

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

1. 3+3
2. 3+2+1
3. 3+1+1+1
4. 2+2+2
5. 2+2+1+1
6. 2+1+1+1+1
7. 1+1+1+1+1+1