7737번 - 삼각분할 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 32 MB4221066632.673%

문제

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

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

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

입력

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

출력

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

예제 입력 1 

5 1000

예제 출력 1 

8
W3sicHJvYmxlbV9pZCI6Ijc3MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBiY1x1YWMwMVx1YmQ4NFx1ZDU2MFx1Yzc3NFx1Yjc4MCBcdWJjZmNcdWI4NWQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMGJjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YmQ4NFx1ZDU2MFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3NDAgXHVhZDUwXHVjYzI4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YzBiY1x1YWMwMVx1YmQ4NFx1ZDU2MFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc3NCBcdWIyZTRcdWI5NzRcdWJhNzQgXHViNDUwIFx1YzBiY1x1YWMwMVx1YmQ4NFx1ZDU2MFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzBiY1x1YWMwMVx1YmQ4NFx1ZDU2MFx1Yzc3NFx1YjJlNC4gKFx1YWYyZFx1YzlkM1x1YzgxMFx1YzVkMCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViOTdjIFx1YmQ5OVx1Yzc3OFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVjNjI0XHVhYzAxXHVkNjE1XHVjNzQ0IFx1YzBiY1x1YWMwMVx1YmQ4NFx1ZDU2MFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjZDFkIFx1YjJlNFx1YzEyZlx1YWMwMFx1YzljMFx1YWMwMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyaS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjRweDsgd2lkdGg6ODQxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VDxzdWI+bjxcL3N1Yj5cdWM3NDQgblx1YWMwMVx1ZDYxNVx1Yzc0NCBcdWMwYmNcdWFjMDFcdWJkODRcdWQ1NjBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1ODhcdWM3NDQgXHViNTRjLCBUPHN1Yj4zPFwvc3ViPiArIFQ8c3ViPjQ8XC9zdWI+ICsgLi4uICsgVDxzdWI+bjxcL3N1Yj5cdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWFjZmMgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgbiAmbGU7IDEwMCwwMDAsIDIgJmxlOyBtICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlQ8c3ViPjM8XC9zdWI+ICsgLi4uICsgVDxzdWI+bjxcL3N1Yj5cdWM3NDQgbVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3NzM3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJpYW5ndWxhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgdHJpYW5ndWxhdGlvbiBvZiBhIG4tdmVydGV4IGNvbnZleCBwb2x5Z29uIGlzIGEgd2F5IG9mIHBhcnRpdGlvbmluZyB0aGUgcG9seWdvbiBpbnRvIHRyaWFuZ2xlcyB1c2luZyBzb21lIG9mIGl0cyBkaWFnb25hbHMgKGluIGEgY29udmV4IHBvbHlnb24gZWFjaCBhbmdsZSBpcyBzbWFsbGVyIHRoYW4gMTgwPHN1cD5vPFwvc3VwPikuIE5vIHR3byBvZiB0aGUgY2hvc2VuIGRpYWdvbmFscyBjYW4gaW50ZXJzZWN0IGF0IGFueSBwb2ludCBkaWZmZXJlbnQgdGhhbiBhbnkgb2YgdGhlIHBvbHlnb24mcnNxdW87cyB2ZXJ0aWNlcy4gVHdvIHRyaWFuZ3VsYXRpb25zIG9mIGEgZ2l2ZW4gcG9seWdvbiBhcmUgY29uc2lkZXJlZCBkaWZmZXJlbnQgaWYgdGhlIHNldHMgb2YgdGhlIGRpYWdvbmFscyB0aGF0IHRoZXkgaW5jbHVkZSBhcmUgZGlmZmVyZW50ICh3ZSBhc3N1bWUgdGhhdCB0aGUgdmVydGljZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuKS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZXJlIGFyZSBcdWZiMDF2ZSBkaWZmZXJlbnQgdHJpYW5ndWxhdGlvbnMgb2YgYW55IGNvbnZleCBwb2x5Z29uIHdpdGggNSB2ZXJ0aWNlczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI0cHg7IHdpZHRoOjg0MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkxldCB1cyBkZW5vdGUgYnkgVDxzdWI+bjxcL3N1Yj4gdGhlIG51bWJlciBvZiB0cmlhbmd1bGF0aW9ucyBvZiBhbnkgbi12ZXJ0ZXggcG9seWdvbi4gWW91ciB0YXNrIGlzIHRvIGNvdW50IFQ8c3ViPjM8XC9zdWI+ICsgVDxzdWI+NDxcL3N1Yj4gKyAuLi4gKyBUPHN1Yj5uPFwvc3ViPi48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHR3byBpbnRlZ2VycyBuIGFuZCBtIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0LDxcL2xpPlxyXG5cdDxsaT5jb3VudHMgdGhlIHJlbWFpbmRlciBvZiBkaXZpc2lvbiBvZiBUPHN1Yj4zPFwvc3ViPiArIC4uLiArIFQ8c3ViPm48XC9zdWI+IGJ5IG0sPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgbiBhbmQgbSAoMyAmbGU7IG4gJmxlOyAxMDAwMDAsIDIgJmxlOyBtICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgJm1kYXNoOyBUPHN1Yj4zPFwvc3ViPiArIC4uLiArIFQ8c3ViPm48XC9zdWI+IG1vZHVsbyBtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UPHN1Yj4zPFwvc3ViPiA9IDEgKG5vIGRpYWdvbmFscyBuZWVkZWQgZm9yIGEgdHJpYW5nbGUpLCBUPHN1Yj40PFwvc3ViPiA9IDIgYW5kIFQ8c3ViPjU8XC9zdWI+ID0gNSAoc2VlIHBpY3R1cmUgYWJvdmUpLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Camp > Czech, Polish and Slovak Preparation Camp > CPSPC 2007 3-3번

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)