시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17253 6920 6004 41.781%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55
W3sicHJvYmxlbV9pZCI6IjI3NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWIyOTQgMFx1YWNmYyAxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gMFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViMjk0IDBcdWM3NzRcdWFjZTAsIDFcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIDJcdWJjODhcdWM5ZjggXHViZDgwXHVkMTMwXHViMjk0IFx1YmMxNFx1Yjg1YyBcdWM1NWUgXHViNDUwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViOTdjIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWMzNjhcdWJjZjRcdWJhNzQgRjxzdWI+bjxcL3N1Yj4gPSBGPHN1Yj5uLTE8XC9zdWI+ICsgRjxzdWI+bi0yPFwvc3ViPiAobiZndDs9MilcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5uPTE3XHVjNzdjXHViNTRjIFx1YWU0Y1x1YzljMCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViOTdjIFx1YzM2OFx1YmNmNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD4wLCAxLCAxLCAyLCAzLCA1LCA4LCAxMywgMjEsIDM0LCA1NSwgODksIDE0NCwgMjMzLCAzNzcsIDYxMCwgOTg3LCAxNTk3PFwvcD5cclxuXHJcbjxwPm5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0Yywgblx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gblx1Yzc0MCA5MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjc0OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYm9uYWNjaSBOdW1iZXIgMiIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEZpYm9uYWNjaSBzZXF1ZW5jZSBpcyBjYWxjdWxhdGVkIGJ5IGFkZGluZyB0aGUgcHJldmlvdXMgdHdvIG51bWJlcnMgb2YgdGhlIHNlcXVlbmNlLiBUaGUgZmlyc3QgdHdvIG51bWJlcnMgaW4gdGhlIEZpYm9uYWNjaSBudW1iZXIgYXJlIDAgYW5kIDEuPFwvcD5cclxuXHJcbjxwPlRoZSBzZXF1ZW5jZSZuYnNwO0ZuIG9mIEZpYm9uYWNjaSBudW1iZXJzIGlzIGRlZmluZWQgYnkgdGhlIHJlY3VycmVuY2UgcmVsYXRpb246IEY8c3ViPm48XC9zdWI+ID0gRjxzdWI+bi0xPFwvc3ViPiArIEY8c3ViPm4tMjxcL3N1Yj4gKG4gJmdlOyAyKS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW50ZWdlciBuLCB3cml0ZSBhIHByb2dyYW0gd2hpY2ggcHJpbnRzIG50aCBGaWJvbmFjY2kgbnVtYmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMmbmJzcDtvbmUgaW50ZWdlciZuYnNwO24uICgxICZsZTsgbiAmbGU7IDkwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgbGluZSBvZiBvbmUgaW50ZWdlciwgbnRoIEZpYm9uYWNjaSBudW1iZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d