시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 36 12 9 36.000%

문제

3 × N개의 점이 찍혀있는 직사각형 그리드가 있다. 그리드 상의 모든 점은 최대 8개의 이웃한 점을 가지고 있다.

그리드 상의 점을 연결해서 만들 수 있는 다각형의 개수를 구하려고 한다. 다각형은 아래와 같은 조건을 만족해야 한다.

꼭짓점은 3 × N개 모두로 이루어져 있어야 한다.
다각형에서 인접한 꼭짓점은 그리드상에서 이웃한 점이어야 한다.
단순 다각형이어야 한다. 즉, 변이 교차하며 안 된다.

아래 그림은 N=6인 경우에 가능한 두 가지 다각형이다.

N이 주어졌을 때, 만들 수 있는 다각형의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 양의 정수 N이 주어진다. (N <= 1,000,000,000).

출력

다각형의 만드는 방법의 수를  1,000,000,000로 나눈 나머지를 출력한다.

예제 입력 1

3

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjI0MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHVjNWYwXHVhY2IwXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4zICZ0aW1lczsgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjYzBkXHVkNjAwXHVjNzg4XHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWI0ZGMgXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTBcdWM3NDAgXHVjZDVjXHViMzAwIDhcdWFjMWNcdWM3NTggXHVjNzc0XHVjNmMzXHVkNTVjIFx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9qai5wbmdcIiBzdHlsZT1cImhlaWdodDoxMThweDsgb3BhY2l0eTowLjk7IHdpZHRoOjEyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YjRkYyBcdWMwYzFcdWM3NTggXHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgMyAmdGltZXM7IE5cdWFjMWMgXHViYWE4XHViNDUwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxiciBcLz5cclxuXHViMmU0XHVhYzAxXHVkNjE1XHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjXHVjMGMxXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YzZjM1x1ZDU1YyBcdWM4MTBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxiciBcLz5cclxuXHViMmU4XHVjMjFjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHViY2MwXHVjNzc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YmE3MCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIE49Nlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9kZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjJweDsgb3BhY2l0eTowLjk7IHdpZHRoOjU3MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gXHUwMDE0Jmx0Oz0gMSwwMDAsMDAwLDAwMCkuPFwvcD5cclxuXHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgJm5ic3A7MSwwMDAsMDAwLDAwMFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNDM0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29ubmVjdGVkIFBvaW50cyIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgYSByZWd1bGFyIGdyaWQgb2YgMyBYIE4gcG9pbnRzLiBFdmVyeSBwb2ludCBpbiB0aGUgZ3JpZCBoYXMgdXAgdG8gZWlnaHQgbmVpZ2hib3JpbmcgcG9pbnRzIChzZWUgRmlnLiAxKS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwOFwvamoucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE4cHg7IHdpZHRoOjEyOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBOZWlnaGJvcmluZyBwb2ludHMgKG1hcmtlZCBieSBhcnJvd3MpLjxcL3A+XHJcblxyXG48cD5XZSBhcmUgaW50ZXJlc3RlZCBpbiBjb3VudGluZyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRvIGNvbm5lY3QgdGhlIHBvaW50cyBvZiB0aGUgZ3JpZCB0byBmb3JtIGEgcG9seWdvbiB0aGF0IGZ1bFx1ZmIwMWxscyB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+VGhlIHNldCBvZiB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbiBjb25zaXN0cyBvZiBhbGwgMyAmdGltZXM7IE4gcG9pbnRzLjxcL2xpPlxyXG5cdDxsaT5BZGphY2VudCB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbiBhcmUgbmVpZ2hib3JpbmcgcG9pbnRzIGluIHRoZSBncmlkLjxcL2xpPlxyXG5cdDxsaT5FYWNoIHBvbHlnb24gaXMgc2ltcGxlLCBpLmUuIHRoZXJlIG11c3Qgbm90IGJlIGFueSBzZWxmLWludGVyc2VjdGlvbnMuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VHdvIHBvc3NpYmxlIHBvbHlnb25zIGZvciBOID0gNiBhcmUgZ2l2ZW4gaW4gdGhlIEZpZy4gMi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTEwOFwvZGQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIycHg7IHdpZHRoOjU3MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgZm9yIGEgZ2l2ZW4gTiB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHdheXMgdG8gY29ubmVjdCB0aGUgcG9pbnRzIGFzIGRlc2NyaWJlZCBtb2R1bG8gMSwwMDAsMDAwLDAwMC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKE4gXHUwMDE0Jmx0Oz0gMSwwMDAsMDAwLDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSB0byBiZSB3cml0dGVuIGNvbnRhaW5zIHRoZSZuYnNwO3JlbWFpbmRlciBvZiB0aGUgbnVtYmVyIG9mIHdheXMgdG8gY29ubmVjdCB0aGUgcG9pbnRzIG1vZHVsbyAxLDAwMCwwMDAsMDAwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 5번