시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 60 11 10 47.619%

문제

삼각 분할이란 볼록 다각형의 대각선을 이용해서 삼각형으로 분할하는 것이다. 두 대각선은 교차할 수 없다. 삼각분할을 이루는 대각선의 집합이 다르면 두 삼각분할은 서로 다른 삼각분할이다. (꼭지점에 1번부터 N번까지 번호를 붙인다)

오각형을 삼각분할하는 방법은 총 다섯가지가 있으며, 아래 그림과 같다.

Tn을 n각형을 삼각분할하는 방법의 수라고 했을 때, T3 + T4 + ... + Tn을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n과 m이 주어진다. (3 ≤ n ≤ 100,000, 2 ≤ m ≤ 109)

출력

T3 + ... + Tn을 m으로 나눈 나머지를 출력한다.

예제 입력 1

5 1000

예제 출력 1

8

힌트

W3sicHJvYmxlbV9pZCI6Ijc3MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBiY1x1YWMwMSBcdWJkODRcdWQ1NjBcdWM3NzRcdWI3ODAgXHViY2ZjXHViODVkIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzBiY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWJkODRcdWQ1NjBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI0NTAgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzQwIFx1YWQ1MFx1Y2MyOFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NzQgXHViMmU0XHViOTc0XHViYTc0IFx1YjQ1MCBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWM3NzRcdWIyZTQuIChcdWFmMmRcdWM5YzBcdWM4MTBcdWM1ZDAgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWJkOTlcdWM3NzhcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1YWMwMVx1ZDYxNVx1Yzc0NCBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1Y2QxZCBcdWIyZTRcdWMxMmZcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI0cHg7IHdpZHRoOjg0MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRuXHVjNzQ0IG5cdWFjMDFcdWQ2MTVcdWM3NDQgXHVjMGJjXHVhYzAxXHViZDg0XHVkNTYwXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgVDMgKyBUNCArIC4uLiArIFRuXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMyAmbGU7IG4gJmxlOyAxMDAsMDAwLCAyICZsZTsgbSAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UMyArIC4uLiArIFRuXHVjNzQ0IG1cdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzczNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyaWFuZ3VsYXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHRyaWFuZ3VsYXRpb24gb2YgYSBuLXZlcnRleCBjb252ZXggcG9seWdvbiBpcyBhIHdheSBvZiBwYXJ0aXRpb25pbmcgdGhlIHBvbHlnb24gaW50byB0cmlhbmdsZXMgdXNpbmcgc29tZSBvZiBpdHMgZGlhZ29uYWxzIChpbiBhIGNvbnZleCBwb2x5Z29uIGVhY2ggYW5nbGUgaXMgc21hbGxlciB0aGFuIDE4MDxzdXA+bzxcL3N1cD4pLiBObyB0d28gb2YgdGhlIGNob3NlbiBkaWFnb25hbHMgY2FuIGludGVyc2VjdCBhdCBhbnkgcG9pbnQgZGlmZmVyZW50IHRoYW4gYW55IG9mIHRoZSBwb2x5Z29uJnJzcXVvO3MgdmVydGljZXMuIFR3byB0cmlhbmd1bGF0aW9ucyBvZiBhIGdpdmVuIHBvbHlnb24gYXJlIGNvbnNpZGVyZWQgZGlmZmVyZW50IGlmIHRoZSBzZXRzIG9mIHRoZSBkaWFnb25hbHMgdGhhdCB0aGV5IGluY2x1ZGUgYXJlIGRpZmZlcmVudCAod2UgYXNzdW1lIHRoYXQgdGhlIHZlcnRpY2VzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbikuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGVyZSBhcmUgXHVmYjAxdmUgZGlmZmVyZW50IHRyaWFuZ3VsYXRpb25zIG9mIGFueSBjb252ZXggcG9seWdvbiB3aXRoIDUgdmVydGljZXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHJpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyNHB4OyB3aWR0aDo4NDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5MZXQgdXMgZGVub3RlIGJ5IFRuIHRoZSBudW1iZXIgb2YgdHJpYW5ndWxhdGlvbnMgb2YgYW55IG4tdmVydGV4IHBvbHlnb24uIFlvdXIgdGFzayBpcyB0byBjb3VudCBUMyArIFQ0ICsgLi4uICsgVG4uPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0d28gaW50ZWdlcnMgbiBhbmQgbSBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+Y291bnRzIHRoZSByZW1haW5kZXIgb2YgZGl2aXNpb24gb2YgVDMgKyAuLi4gKyBUbiBieSBtLDxcL2xpPlxyXG5cdDxsaT53cml0ZXMgdGhlIHJlc3VsdCB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIG0gKDMgJmxlOyBuICZsZTsgMTAwMDAwLCAyICZsZTsgbSAmbGU7IDEwPHN1cD45PFwvc3VwPiksIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyICZtZGFzaDsgVDMgKyAuLi4gKyBUbiBtb2R1bG8gbS48XC9wPlxyXG4iLCJoaW50IjoiPHA+VDMgPSAxIChubyBkaWFnb25hbHMgbmVlZGVkIGZvciBhIHRyaWFuZ2xlKSwgVDQgPSAyIGFuZCBUNSA9IDUgKHNlZSBwaWN0dXJlIGFib3ZlKS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Camp > Czech, Polish and Slovak Preparation Camp > CPSPC 2007 33번