시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+PFwvcD5cclxuXHJcbjxwPk5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKE4gXHUwMDE0Jmx0Oz0gMSwwMDAsMDAwLDAwMCkuPFwvcD5cclxuXHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgJm5ic3A7MSwwMDAsMDAwLDAwMFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25uZWN0ZWQgUG9pbnRzIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIHJlZ3VsYXIgZ3JpZCBvZiAzIFggTiBwb2ludHMuIEV2ZXJ5IHBvaW50IGluIHRoZSBncmlkIGhhcyB1cCB0byBlaWdodCBuZWlnaGJvcmluZyBwb2ludHMgKHNlZSBGaWcuIDEpLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9qai5wbmdcIiBzdHlsZT1cImhlaWdodDoxMThweDsgd2lkdGg6MTI5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IE5laWdoYm9yaW5nIHBvaW50cyAobWFya2VkIGJ5IGFycm93cykuPFwvcD5cclxuXHJcbjxwPldlIGFyZSBpbnRlcmVzdGVkIGluIGNvdW50aW5nIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gY29ubmVjdCB0aGUgcG9pbnRzIG9mIHRoZSBncmlkIHRvIGZvcm0gYSBwb2x5Z29uIHRoYXQgZnVsXHVmYjAxbGxzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGUgc2V0IG9mIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIGNvbnNpc3RzIG9mIGFsbCAzICZ0aW1lczsgTiBwb2ludHMuPFwvbGk+XHJcblx0PGxpPkFkamFjZW50IHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIGFyZSBuZWlnaGJvcmluZyBwb2ludHMgaW4gdGhlIGdyaWQuPFwvbGk+XHJcblx0PGxpPkVhY2ggcG9seWdvbiBpcyBzaW1wbGUsIGkuZS4gdGhlcmUgbXVzdCBub3QgYmUgYW55IHNlbGYtaW50ZXJzZWN0aW9ucy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Ud28gcG9zc2libGUgcG9seWdvbnMgZm9yIE4gPSA2IGFyZSBnaXZlbiBpbiB0aGUgRmlnLiAyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9kZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjJweDsgd2lkdGg6NTcxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyBmb3IgYSBnaXZlbiBOIHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyB0byBjb25uZWN0IHRoZSBwb2ludHMgYXMgZGVzY3JpYmVkIG1vZHVsbyAxLDAwMCwwMDAsMDAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgY29udGFpbnMgb25lIHBvc2l0aXZlIGludGVnZXIgTiAoTiBcdTAwMTQmbHQ7PSAxLDAwMCwwMDAsMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIHRvIGJlIHdyaXR0ZW4gY29udGFpbnMgdGhlJm5ic3A7cmVtYWluZGVyIG9mIHRoZSBudW1iZXIgb2Ygd2F5cyB0byBjb25uZWN0IHRoZSBwb2ludHMgbW9kdWxvIDEsMDAwLDAwMCwwMDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 5번