시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB48442262188946.017%

문제

회의가 끝났고, 이제 악수를 하는 시간이다. 모든 사람은 직사각형 탁자 하나의 한 면에 앉아있다.

자리를 벗어나지 않고 악수를 하는 방법의 수는 총 몇 가지일까?

각 사람들은 자신의 왼쪽이나 오른쪽에 있는 사람들과 악수를 할 수 있다. (안 할 수도 있다)

입력

첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다.

출력

첫째 줄에 악수를 하는 방법의 수를 출력한다. 수가 매우 커질 수 있기 때문에, 마지막 자리만 출력한다.

예제 입력 1

4

예제 출력 1

5

힌트

n=4인 경우에는 5가지 방법이 있다.

W3sicHJvYmxlbV9pZCI6IjgzOTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDVcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDY4Y1x1Yzc1OFx1YWMwMCBcdWIwNWRcdWIwYWNcdWFjZTAsIFx1Yzc3NFx1YzgxYyBcdWM1NDVcdWMyMThcdWI5N2MgXHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHVkMGMxXHVjNzkwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQ1NWMgXHViYTc0XHVjNWQwIFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHViOWFjXHViOTdjIFx1YmM5N1x1YzViNFx1YjA5OFx1YzljMCBcdWM1NGFcdWFjZTAgXHVjNTQ1XHVjMjE4XHViOTdjIFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViMjk0IFx1Y2QxZCBcdWJhODcgXHVhYzAwXHVjOWMwXHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM3NzRcdWIwOTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWFjZmMgXHVjNTQ1XHVjMjE4XHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiAoXHVjNTQ4IFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0KTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ2OGNcdWM3NThcdWM1ZDAgXHVjYzM4XHVjMTFkXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMTggbiAoMSAmbGU7IG4gJmxlOyAxMCwwMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM1NDVcdWMyMThcdWI5N2MgXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWMyMThcdWFjMDAgXHViOWU0XHVjNmIwIFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViOWM4XHVjOWMwXHViOWM5IFx1Yzc5MFx1YjlhY1x1YjljYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva29uLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExMXB4OyB3aWR0aDoxMDJweFwiIFwvPjxcL3A+XHJcblxyXG48cD5uPTRcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDVcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjgzOTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25ncmVzcyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHBhcnRpY2lwYW50cyBvZiB0aGUgZmlyc3QgY29uZ3Jlc3Mgb2YgUGFyYW5vaWFjIEluZm9ybWF0aWNzIFNvY2lldHkgdG9vayB0aGVpciBwbGFjZXMgYXQgYSByZWN0YW5ndWxhciB0YWJsZS4gQWxsIHNhdCBhdCB0aGUgc2FtZSBzaWRlLiBPbmUgb2YgdGhlbSBwb3NlIHRoZSBmb2xsb3dpbmcgcXVlc3Rpb246ICZxdW90O1doYXQgaXMgdGhlIG51bWJlciBvZiB3YXlzIHdlIGNhbiBzaGFrZSBvdXIgaGFuZHMgd2l0aG91dCBsZWF2aW5nIG91ciBwbGFjZXM/IEVhY2ggdGltZSBldmVyeSBwYXJ0aWNpcGFudCBjYW4gc2hha2UgaGFuZCBvZiBvbmUgcGVyc29uIGFuZCB0aGlzIHBlcnNvbiBtdXN0IGJlIGhpc1wvaGVyIG5laWdoYm91ci4mcXVvdDs8XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIGNvbmdyZXNzIHBhcnRpY2lwYW50cyBhcmUgdGhlb3JldGljaWFucywgdGhleSBhc2tlZCB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtLCB3aGljaCBjb21wdXRlcyB0aGlzIG51bWJlciBvZiB3YXlzLiBUaGUgcGFydGljaXBhbnRzIGhhdGUgYmlnIG51bWJlcnMsIHNvIHRoZXkgbmVlZCBvbmx5IHRoZSBsYXN0IGRpZ2l0IG9mIHRoZSByZXN1bHQuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgbnVtYmVyIG9mIGNvbmdyZXNzIHBhcnRpY2lwYW50cyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+Y29tcHV0ZXMgdGhlIGxhc3QgZGlnaXQgb2YgdGhlIG51bWJlciBvZiB3YXlzIHRoZSBwYXJ0aWNpcGFudHMgY2FuIHNoYWtlIGhhbmRzLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIGFuc3dlciB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxMCAwMDAgMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBkaWdpdCwgaS5lLiB0aGUgbGFzdCBkaWdpdCBvZiB0aGUgbnVtYmVyIG9mIHdheXMgdGhlIHBhcnRpY2lwYW50cyBjYW4gc2hha2UgaGFuZHMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Algorithmic Engagements > PA 2006 1-1번