문제
상근이는 오른쪽 그림과 같은 미로에 갇혀있다. 미로는 육각형 모양의 방이 계속해서 붙어있는 모양이고, 이러한 방은 무수히 많이 있다. 또, 인접한 방은 문으로 연결되어 있어서, 한 방에서 다른 방으로 건너갈 수 있다. 하지만, 방의 개수는 무한대이기 때문에, 상근이는 절대 이 미로를 빠져나갈 수 없다.
오른쪽 그림에 상근이가 있는 방이 표시되어 있다. 이때, 상근이가 있는 방에서 시작해서 방을 n번 이동해서, 다시 원래 있던 방으로 돌아오는 경로의 수를 구하려고 한다.
출력
각 테스트 케이스에 대해서, 입력으로 주어진 n에 해당하는 경로의 개수를 출력한다. 정답은 항상 231보다 작다.
W3sicHJvYmxlbV9pZCI6IjUwNjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiZjhcdWI4NWNcdWM1ZDAgXHVhYzA3XHVkNzhjIFx1YzBjMVx1YWRmYyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9oZXgucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjI5MnB4OyB3aWR0aDoyNjhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYmY4XHViODVjXHVjNWQwIFx1YWMwN1x1ZDYwMFx1Yzc4OFx1YjJlNC4gXHViYmY4XHViODVjXHViMjk0IFx1YzcyMVx1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHViYzI5XHVjNzc0IFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWJkOTlcdWM1YjRcdWM3ODhcdWIyOTQgXHViYWE4XHVjNTkxXHVjNzc0XHVhY2UwLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViYzI5XHVjNzQwIFx1YmIzNFx1YzIxOFx1ZDc4OCBcdWI5Y2VcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJjMjlcdWM3NDAgXHViYjM4XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWMxMWMsIFx1ZDU1YyBcdWJjMjlcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWFjNzRcdWIxMDhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJjMjlcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MDhcdWIzMDAgXHVjNzc0IFx1YmJmOFx1Yjg1Y1x1Yjk3YyBcdWJlNjBcdWM4MzhcdWIwOThcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc3NCBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYyBcdWJjMjlcdWM3NDQgblx1YmM4OCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWMxMWMsJm5ic3A7XHViMmU0XHVjMmRjIFx1YzZkMFx1Yjc5OCBcdWM3ODhcdWIzNTggXHViYzI5XHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyNFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBuXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgxICZsZTsgbiAmbGU7IDE0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBuXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSAyPHN1cD4zMTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUwNjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb25leWNvbWIgV2FsayIsImRlc2NyaXB0aW9uIjoiPHA+QSBiZWUgbGFydmEgbGl2aW5nIGluIGEgaGV4YWdvbmFsIGNlbGwgb2YgYSBsYXJnZSBob25leWNvbWIgZGVjaWRlcyB0byBjcmVlcCBmb3IgYSB3YWxrLiBJbiBlYWNoICZsZHF1bztzdGVwJnJkcXVvOyB0aGUgbGFydmEgbWF5IG1vdmUgaW50byBhbnkgb2YgdGhlIHNpeCBhZGphY2VudCBjZWxscyBhbmQgYWZ0ZXIgbiBzdGVwcywgaXQgaXMgdG8gZW5kIHVwIGluIGl0cyBvcmlnaW5hbCBjZWxsLjxcL3A+XHJcblxyXG48cD5Zb3VyIHByb2dyYW0gaGFzIHRvIGNvbXB1dGUsIGZvciBhIGdpdmVuIG4sIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHN1Y2ggbGFydmEgd2Fsa3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIGNhc2UgY29uc2lzdHMgb2Ygb25lIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG4sIHdoZXJlIDEgJmxlOyBuICZsZTsgMTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIHdhbGtzLiBVbmRlciB0aGUgYXNzdW1wdGlvbiAxICZsZTsgbiAmbGU7IDE0LCB0aGUgYW5zd2VyIHdpbGwgYmUgbGVzcyB0aGFuIDI8c3VwPjMxPFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d