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

문제

CTP마을에 사는 토끼 아람이는 3,2,1미터씩 뛰어서 n미터를 지난다. 람토끼가 지나야하야 하는 길이가 주어졌을 때 점프 길이가 증가하지 않는 순서로 지나가는 방법은 총 몇 가지가 있을까?

찾을 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

n이 표준입력으로 들어온다. (1 ≤ n ≤ 109)

출력

프로그램의 결과값을 표준출력으로 나타내시오. 값은 1000000으로 나눈 나머지를 출력하시오

예제 입력 1

6

예제 출력 1

7

힌트

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
W3sicHJvYmxlbV9pZCI6IjMzNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlNjFcdWNkMWRcdWFlNjFcdWNkMWQiLCJkZXNjcmlwdGlvbiI6IjxwPkNUUFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYWNcdWIyOTQgXHVkMWEwXHViMDdjJm5ic3A7XHVjNTQ0XHViNzhjXHVjNzc0XHViMjk0IDMsMiwxXHViYmY4XHVkMTMwXHVjNTI5IFx1YjZmMFx1YzViNFx1YzExYyBuXHViYmY4XHVkMTMwXHViOTdjIFx1YzljMFx1YjA5Y1x1YjJlNC4gXHViNzhjXHVkMWEwXHViMDdjXHVhYzAwIFx1YzljMFx1YjA5OFx1YzU3Y1x1ZDU1OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVjODEwXHVkNTA0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0Jm5ic3A7XHVjMjFjXHVjMTFjXHViODVjJm5ic3A7XHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCZuYnNwO1x1Y2QxZCBcdWJhODcgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG5cclxuPHA+XHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5uXHVjNzc0IFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuICgxICZsZTsgbiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVhY2IwXHVhY2ZjXHVhYzEyXHVjNzQ0IFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWMyZGNcdWM2MjQuIFx1YWMxMlx1Yzc0MCAxMDAwMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0PFwvcD5cclxuIiwiaGludCI6IjxwPjEsMiwzXHVjNzQ0IFx1YjM1NFx1ZDU3NFx1YzExYyA2XHVjNzc0IFx1YjQxOFx1YmE3NFx1YzExYyBcdWM5OWRcdWFjMDBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YjJlNFx1Yzc0YyA3XHVhYzAwXHVjOWMwIFx1Yzc3NFx1YjJlNC4gN1x1Yzc0NCZuYnNwOzEwMDAwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yzc3OCA3XHVjNzc0IFx1Y2Q5Y1x1YjgyNVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+MyszPFwvbGk+XHJcblx0PGxpPjMrMisxPFwvbGk+XHJcblx0PGxpPjMrMSsxKzE8XC9saT5cclxuXHQ8bGk+MisyKzI8XC9saT5cclxuXHQ8bGk+MisyKzErMTxcL2xpPlxyXG5cdDxsaT4yKzErMSsxKzE8XC9saT5cclxuXHQ8bGk+MSsxKzErMSsxKzE8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzM2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikp1bXBzIiwiZGVzY3JpcHRpb24iOiI8cD5BIGJ1bm55IGhhcyB0byBwYXNzIG4gbWV0ZXJzIHdpdGgganVtcHMgb2YgbGVuZ3RocyAzLCAyIG9yIDEgbWV0ZXJzLiBJbiBob3cgbWFueSBkaWZmZXJlbnQgd2F5cyB0aGlzIGNhbiBiZSBkb25lLCBpZiB0aGUgbGVuZ3RocyBvZiBzdWNjZXNzaXZlIGp1bXBzIGZvcm0gYSBub24taW5jcmVhc2luZyBzZXF1ZW5jZT8gV3JpdGUgcHJvZ3JhbSBqdW1wcywgd2hpY2ggY29tcHV0ZXMgdGhlIG51bWJlciB3ZSBhcmUgbG9va2luZyBmb3IuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgdmFsdWUgb2YgbiBzaG91bGQgYmUgZW50ZXJlZCBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCAoMSAmbGU7IG4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBwcm9ncmFtIHNob3VsZCB3cml0ZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0IG9uZSBpbnRlZ2VyLCBlcXVhbCB0byB0aGUgcmVtYWluZGVyIG9mIHRoZSBmb3VuZCBudW1iZXIsIGRpdmlkZWQgYnkgMTAwMDAwMC48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyBpcyA3LCBhbmQgaXRzIHJlbWFpbmRlciBtb2R1bG8gMTAwMDAwMCBpcyBhbHNvIDcuIFRoZSBkaWZmZXJlbnQgc2VxdWVuY2VzIG9mIGp1bXBzIGFyZTo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4zKzM8XC9saT5cclxuXHQ8bGk+MysyKzE8XC9saT5cclxuXHQ8bGk+MysxKzErMTxcL2xpPlxyXG5cdDxsaT4yKzIrMjxcL2xpPlxyXG5cdDxsaT4yKzIrMSsxPFwvbGk+XHJcblx0PGxpPjIrMSsxKzErMTxcL2xpPlxyXG5cdDxsaT4xKzErMSsxKzErMSZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d