시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 35 11 8 33.333%

문제

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+XHJcblxyXG48cD5cdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgMyAmdGltZXM7IE5cdWFjMWMgXHViYWE4XHViNDUwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxiciBcLz5cclxuXHViMmU0XHVhYzAxXHVkNjE1XHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDAgXHVhZGY4XHViOWFjXHViNGRjXHVjMGMxXHVjNWQwXHVjMTFjIFx1Yzc3NFx1YzZjM1x1ZDU1YyBcdWM4MTBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxiciBcLz5cclxuXHViMmU4XHVjMjFjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHViY2MwXHVjNzc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YmE3MCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgTj02XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViNDUwIFx1YWMwMFx1YzljMCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDhcL2RkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6NTcxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoTiBcdTAwMTQmbHQ7PSAxLDAwMCwwMDAsMDAwKS48XC9wPlxyXG5cclxuXHJcbiIsIm91dHB1dCI6IjxwPlx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAmbmJzcDsxLDAwMCwwMDAsMDAwXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25uZWN0ZWQgUG9pbnRzIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIHJlZ3VsYXIgZ3JpZCBvZiAzIFggTiBwb2ludHMuIEV2ZXJ5IHBvaW50IGluIHRoZSBncmlkIGhhcyB1cCB0byBlaWdodCBuZWlnaGJvcmluZyBwb2ludHMgKHNlZSBGaWcuIDEpLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9qai5wbmdcIiBzdHlsZT1cImhlaWdodDoxMThweDsgd2lkdGg6MTI5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDE6IE5laWdoYm9yaW5nIHBvaW50cyAobWFya2VkIGJ5IGFycm93cykuPFwvcD5cclxuXHJcbjxwPldlIGFyZSBpbnRlcmVzdGVkIGluIGNvdW50aW5nIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gY29ubmVjdCB0aGUgcG9pbnRzIG9mIHRoZSBncmlkIHRvIGZvcm0gYSBwb2x5Z29uIHRoYXQgZnVsXHVmYjAxbGxzIHRoZSBmb2xsb3dpbmcgY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGUgc2V0IG9mIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIGNvbnNpc3RzIG9mIGFsbCAzICZ0aW1lczsgTiBwb2ludHMuPFwvbGk+XHJcblx0PGxpPkFkamFjZW50IHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIGFyZSBuZWlnaGJvcmluZyBwb2ludHMgaW4gdGhlIGdyaWQuPFwvbGk+XHJcblx0PGxpPkVhY2ggcG9seWdvbiBpcyBzaW1wbGUsIGkuZS4gdGhlcmUgbXVzdCBub3QgYmUgYW55IHNlbGYtaW50ZXJzZWN0aW9ucy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Ud28gcG9zc2libGUgcG9seWdvbnMgZm9yIE4gPSA2IGFyZSBnaXZlbiBpbiB0aGUgRmlnLiAyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA4XC9kZC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjJweDsgd2lkdGg6NTcxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyBmb3IgYSBnaXZlbiBOIHRoZSBudW1iZXIgb2YgcG9zc2libGUgd2F5cyB0byBjb25uZWN0IHRoZSBwb2ludHMgYXMgZGVzY3JpYmVkIG1vZHVsbyAxLDAwMCwwMDAsMDAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgY29udGFpbnMgb25lIHBvc2l0aXZlIGludGVnZXIgTiAoTiBcdTAwMTQmbHQ7PSAxLDAwMCwwMDAsMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIHRvIGJlIHdyaXR0ZW4gY29udGFpbnMgdGhlJm5ic3A7cmVtYWluZGVyIG9mIHRoZSBudW1iZXIgb2Ygd2F5cyB0byBjb25uZWN0IHRoZSBwb2ludHMgbW9kdWxvIDEsMDAwLDAwMCwwMDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 5번