시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB45181340.625%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

3

예제 출력 1

8

예제 입력 2

4

예제 출력 2

40
W3sicHJvYmxlbV9pZCI6IjI0MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTAgXHVjNWYwXHVhY2IwXHVkNTU4XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4zICZ0aW1lczsgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjYzBkXHVkNjAwXHVjNzg4XHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkZjhcdWI5YWNcdWI0ZGNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWI0ZGMgXHVjMGMxXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWM4MTBcdWM3NDAgXHVjZDVjXHViMzAwIDhcdWFjMWNcdWM3NTggXHVjNzc0XHVjNmMzXHVkNTVjIFx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzI0NjNhZWViLWNjYzctNGJlYS05NzVjLTYwODBiZDg1ZmFmYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTA2cHg7IGhlaWdodDogMTA1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjlhY1x1YjRkYyBcdWMwYzFcdWM3NTggXHVjODEwXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0MCAzICZ0aW1lczsgTlx1YWMxYyBcdWJhYThcdWI0NTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1YWMwMVx1ZDYxNVx1YzVkMFx1YzExYyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwIFx1YWRmOFx1YjlhY1x1YjRkY1x1YzBjMVx1YzVkMFx1YzExYyBcdWM3NzRcdWM2YzNcdWQ1NWMgXHVjODEwXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU4XHVjMjFjIFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHViY2MwXHVjNzc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YmE3MCBcdWM1NDggXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgTj02XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViNDUwIFx1YWMwMFx1YzljMCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYTdlZTExZGUtM2VkYy00YTZkLWE2YzMtZGIzMDdkNWMxN2MxXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1NDVweDsgaGVpZ2h0OiAxMDVweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoTiAmbGU7IDEsMDAwLDAwMCwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc1OCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAmbmJzcDsxLDAwMCwwMDAsMDAwXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI0MzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb25uZWN0ZWQgUG9pbnRzIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciBhIHJlZ3VsYXIgZ3JpZCBvZiAzIFggTiBwb2ludHMuIEV2ZXJ5IHBvaW50IGluIHRoZSBncmlkIGhhcyB1cCB0byBlaWdodCBuZWlnaGJvcmluZyBwb2ludHMgKHNlZSBGaWcuIDEpLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzI0NjNhZWViLWNjYzctNGJlYS05NzVjLTYwODBiZDg1ZmFmYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMTA2cHg7IGhlaWdodDogMTA1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxOiBOZWlnaGJvcmluZyBwb2ludHMgKG1hcmtlZCBieSBhcnJvd3MpLjxcL3A+XHJcblxyXG48cD5XZSBhcmUgaW50ZXJlc3RlZCBpbiBjb3VudGluZyB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRvIGNvbm5lY3QgdGhlIHBvaW50cyBvZiB0aGUgZ3JpZCB0byBmb3JtIGEgcG9seWdvbiB0aGF0IGZ1bFx1ZmIwMWxscyB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+VGhlIHNldCBvZiB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbiBjb25zaXN0cyBvZiBhbGwgMyAmdGltZXM7IE4gcG9pbnRzLjxcL2xpPlxyXG5cdDxsaT5BZGphY2VudCB2ZXJ0aWNlcyBvZiB0aGUgcG9seWdvbiBhcmUgbmVpZ2hib3JpbmcgcG9pbnRzIGluIHRoZSBncmlkLjxcL2xpPlxyXG5cdDxsaT5FYWNoIHBvbHlnb24gaXMgc2ltcGxlLCBpLmUuIHRoZXJlIG11c3Qgbm90IGJlIGFueSBzZWxmLWludGVyc2VjdGlvbnMuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VHdvIHBvc3NpYmxlIHBvbHlnb25zIGZvciBOID0gNiBhcmUgZ2l2ZW4gaW4gdGhlIEZpZy4gMi48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9hN2VlMTFkZS0zZWRjLTRhNmQtYTZjMy1kYjMwN2Q1YzE3YzFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDU0NXB4OyBoZWlnaHQ6IDEwNXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIGZvciBhIGdpdmVuIE4gdGhlIG51bWJlciBvZiBwb3NzaWJsZSB3YXlzIHRvIGNvbm5lY3QgdGhlIHBvaW50cyBhcyBkZXNjcmliZWQgbW9kdWxvIDEsMDAwLDAwMCwwMDAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBjb250YWlucyBvbmUgcG9zaXRpdmUgaW50ZWdlciBOIChOICZsZTsgMSwwMDAsMDAwLDAwMCkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSB0byBiZSB3cml0dGVuIGNvbnRhaW5zIHRoZSZuYnNwO3JlbWFpbmRlciBvZiB0aGUgbnVtYmVyIG9mIHdheXMgdG8gY29ubmVjdCB0aGUgcG9pbnRzIG1vZHVsbyAxLDAwMCwwMDAsMDAwLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 5번