시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB112144230840.741%

문제

피보나치(Fibonacci) 수열은 매우 유명한 수열로 그 점화식은 F[i]=F[i-1]+F[i-2]와 같이 표현된다. 우리는 이와 같은 수열을 살짝 변경한 피보나치(Pibonacci) 수열에 대해 살펴보자. 피보나치 수열의 점화식은 아래와 같다.

  • P[n] = 1 (0 ≤ n ≤ π)
  • P[n] = P[n-1] + P[n-π] (그 외)

주의할 것은 n이 꼭 정수일 필요는 없다는 것이다. 즉, P[n-π] = P[n-π-1]+P[n-π-π]와 같은 식으로 계산을 해 주어야 한다.

자연수로 n이 주어졌을 때, P[n]을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(1 ≤ n ≤ 1,000)이 주어진다.

출력

첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

10

예제 출력 1

19
W3sicHJvYmxlbV9pZCI6IjE3MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJQaWJvbmFjY2kiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OChGaWJvbmFjY2kpIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWFkZjggXHVjODEwXHVkNjU0XHVjMmRkXHVjNzQwIEZbaV09RltpLTFdK0ZbaS0yXVx1YzY0MCBcdWFjMTlcdWM3NzQgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMGI0XHVjOWRkIFx1YmNjMFx1YWNiZFx1ZDU1YyBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTgoUGlib25hY2NpKSBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC4gXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM4MTBcdWQ2NTRcdWMyZGRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5QW25dID0gMSAoMCAmbGU7IG4gJmxlOyAmcGk7KTxcL2xpPlxyXG5cdDxsaT5QW25dID0gUFtuLTFdICsgUFtuLSZwaTtdIChcdWFkZjggXHVjNjc4KTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzhmY1x1Yzc1OFx1ZDU2MCBcdWFjODNcdWM3NDAgblx1Yzc3NCBcdWFmMmQgXHVjODE1XHVjMjE4XHVjNzdjIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM5ODksIFBbbi0mcGk7XSA9IFBbbi0mcGk7LTFdK1Bbbi0mcGk7LSZwaTtdXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVhY2M0XHVjMGIwXHVjNzQ0IFx1ZDU3NCBcdWM4ZmNcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBQW25dXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3OTBcdWM1ZjBcdWMyMTggbigxICZsZTsgbiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBQW25dXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzEyXHVjNzc0IFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyAxLDAwMCwwMDAsMDAwLDAwMCwwMDAsMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3MzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaWJvbmFjY2kiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBtaWdodCBoYXZlIGhlYXJkIG9mIHRoZSBGaWJvbmFjY2kgbnVtYmVycyBhbmQgb2YgdGhlIG51bWJlciBwaS4gSWYgeW91IGxldCB0aGVzZSB0d28gaWRlYXMgbWVyZ2UsIGEgbmV3IGFuZCBlc290ZXJpYyBjb25jZXB0IGNvbWVzIGludG8gYmVpbmc6IHRoZSBQaWJvbmFjY2kgbnVtYmVycy4gVGhlc2UgY2FuIGJlIGRlZmluZWQgZm9yIHJlYWwgeCAmZ2U7IDAgYnk6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+UCh4KSA9IDEgKGZvciAwICZsZTsgeCAmbHQ7IDQpPFwvbGk+XHJcblx0PGxpPlAoeCkgPSBQKHgtMSkgKyBQKHgtcGkpIChmb3IgNCAmbGU7IHgpLDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPndoZXJlIHBpID0gMy4xNDE1OTI2NTM1Li4uIEluIHRoaXMgcHJvYmxlbSwgeW91IGFyZSBhc2tlZCB0byBjb21wdXRlIFAoeCkgZm9yIGEgZ2l2ZW4geC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHNldmVyYWwgbm9uLW5lZ2F0aXZlIHJlYWwgbnVtYmVycyBlYWNoIG9uIGEgc2VwYXJhdGUgbGluZS4gVGhlIGxhc3QgbGluZSBjb250YWlucyAtMSBtYXJraW5nIHRoZSBlbmQgb2YgdGhlIGlucHV0IGZpbGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbm9uLW5lZ2F0aXZlIHJlYWwgbnVtYmVyIGluIHRoZSBpbnB1dCBmaWxlLCBvdXRwdXQgdGhlIGNvcnJlc3BvbmRpbmcgUGlib25hY2NpIG51bWJlci4gU2hvdWxkIHRoZSBQaWJvbmFjY2kgbnVtYmVyIGJlIG1vcmUgdGhhbiA1MCBkaWdpdHMgbG9uZywgZGl2aWRlIGl0IG9uIHRoZSBjb25zZWN1dGl2ZSBsaW5lcywgb3V0cHV0dGluZyA1MCBkaWdpdHMgb24gZWFjaCAodGhlIGxhc3QgbGluZSBtYXkgY29udGFpbiBsZXNzIGRpZ2l0cykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Internet Problem Solving Contest > IPSC 2001 F번

  • 문제를 번역한 사람: author5