시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 187 89 78 53.061%

문제

그래프 이론에서 매칭(또는 독립 간선 집합)은 공통 정점을 가지지 않는 간선의 집합을 말한다.

그래프 G = (V,E)가 주어졌을 때, M이 G의 매칭이 되기 위해서는 M이 E의 부분 집합이면서, M에 포함되는 간선이 같은 정점을 공유하지 않아야 한다.

사이클 그래프 Cn, n ≥ 3 은 단순 무방향 그래프이고, 정점의 집합은 {1,...,n}, 간선의 집합 E(Cn) = {{a,b} | |a-b| ≡ 1 mod n}이다. 또, 2-정규 그래프이며, 간선의 수는 n개 이다. C3, C4, C5, C6은 아래 그림에 나와있다.

사이클 그래프 Cn에서 매칭의 수를 구하는 프로그램을 작성하시오.

위의 그림은 C4의 모든 매칭을 나타낸 그림이다. 매칭에 해당하는 간선은 초록색으로 표시되어 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 양의 정수 n으로 이루어져 있다. (3 ≤ n ≤ 10000)

출력

각 테스트 케이스에 대해서 Cn의 매칭의 개수를 출력한다.

예제 입력 1

3
4
100

예제 출력 1

4
7
792070839848372253127
W3sicHJvYmxlbV9pZCI6IjM2NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI3OThcdWQ1MDQgXHViOWU0XHVjZTZkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFkZjhcdWI3OThcdWQ1MDQgXHVjNzc0XHViODYwXHVjNWQwXHVjMTFjIFx1YjllNFx1Y2U2ZChcdWI2MTBcdWIyOTQgXHViM2M1XHViOWJkIFx1YWMwNFx1YzEyMCBcdWM5ZDFcdWQ1NjkpXHVjNzQwIFx1YWNmNVx1ZDFiNSBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhYzAwXHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViNzk4XHVkNTA0IEcgPSAoVixFKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBNXHVjNzc0IEdcdWM3NTggXHViOWU0XHVjZTZkXHVjNzc0IFx1YjQxOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgTVx1Yzc3NCBFXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWM5ZDFcdWQ1NjlcdWM3NzRcdWJhNzRcdWMxMWMsIE1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjODEwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWM3NzRcdWQwNzQgXHVhZGY4XHViNzk4XHVkNTA0IEM8c3ViPm48XC9zdWI+LCBuICZnZTsgMyBcdWM3NDAgXHViMmU4XHVjMjFjIFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWFjZTAsIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDAgezEsLi4uLG59LCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjOWQxXHVkNTY5IEUoQzxzdWI+bjxcL3N1Yj4pID0ge3thLGJ9IHwgfGEtYnwgJmVxdWl2OyAxIG1vZCBufVx1Yzc3NFx1YjJlNC4gXHViNjEwLCAyLVx1YzgxNVx1YWRkYyBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWJhNzAsIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMThcdWIyOTQgblx1YWMxYyBcdWM3NzRcdWIyZTQuIEM8c3ViPjM8XC9zdWI+LCBDPHN1Yj40PFwvc3ViPiwgQzxzdWI+NTxcL3N1Yj4sIEM8c3ViPjY8XC9zdWI+XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2MxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2N3B4OyB3aWR0aDo2MjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWM3NzRcdWQwNzQgXHVhZGY4XHViNzk4XHVkNTA0IEM8c3ViPm48XC9zdWI+XHVjNWQwXHVjMTFjIFx1YjllNFx1Y2U2ZFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYzIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE3cHg7IHdpZHRoOjYxM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM3NDAgQzxzdWI+NDxcL3N1Yj5cdWM3NTggXHViYWE4XHViNGUwIFx1YjllNFx1Y2U2ZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjggXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LiBcdWI5ZTRcdWNlNmRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWNkMDhcdWI4NWRcdWMwYzlcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgzICZsZTsgbiAmbGU7IDEwMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBDPHN1Yj5uPFwvc3ViPlx1Yzc1OCBcdWI5ZTRcdWNlNmRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRWRnZSBDYXNlIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBncmFwaCB0aGVvcnksIGEgbWF0Y2hpbmcgb3IgaW5kZXBlbmRlbnQgZWRnZSBzZXQgaW4gYSBncmFwaCBHID0gKFYsJm5ic3A7RSkgaXMgYSBzZXQgb2YgZWRnZXMgTSAmc3ViZTsmbmJzcDtFIHN1Y2ggdGhhdCBubyB0d28gZWRnZXMgaW4gdGhlIG1hdGNoaW5nIE0gc2hhcmUgYSBjb21tb24gdmVydGV4LjxcL3A+XHJcblxyXG48cD5SZWNlbnRseSB5b3Ugc2F3IGluIHRoZSBuZXdzIHRoYXQgJmxkcXVvO1RoZSBTdmVyaWdlcyBSaWtzYmFuayBQcml6ZSBpbiBFY29ub21pYyBTY2llbmNlcyBpbiBNZW1vcnkgb2YgQWxmcmVkIE5vYmVsJnJkcXVvOyAoaW5mb3JtYWxseSwgdGhlIE5vYmVsIFByaXplIGluIEVjb25vbWljcykgZm9yIDIwMTIgd2FzIGF3YXJkZWQgdG8gQWx2aW4gRS4gUm90aCBhbmQgTGxveWQgUy4gU2hhcGxleSBmb3IsIGFtb25nc3Qgb3RoZXIgdGhpbmdzLCB0aGVpciBhbGdvcml0aG0gZm9yIFx1ZmIwMW5kaW5nIGEgbWF0Y2hpbmcgc2F0aXNmeWluZyBjZXJ0YWluIGNyaXRlcmlhIGluIGEgYmlwYXJ0aXRlIGdyYXBoLiBTaW5jZSB5b3UgaGF2ZSBhbHNvIGhlYXJkIHRoYXQgbWF0Y2hpbmdzIGluIGN5Y2xlIGdyYXBocyBoYXZlIGFwcGxpY2F0aW9ucyBpbiBjaGVtaXN0cnkgeW91ciB0aG91Z2h0cyBjZW50ckluIGdyYXBoIHRoZW9yeSwgYSBtYXRjaGluZyBvciBpbmRlcGVuZGVudCBlZGdlIHNldCBpbiBhIGdyYXBoIEcgPSAoViwmbmJzcDtFKSBpcyBhIHNldCBvZiBlZGdlcyBNIFx1MDAxMiBFIHN1Y2ggdGhhdCBubyB0d28gZWRnZXMgaW4gdGhlIG1hdGNoaW5nIE0gc2hhcmUgYSBjb21tb24gdmVydGV4LmUgYXJvdW5kIGEgcGxhbiBmb3IgYSBiZWF1dGlmdWwgZnV0dXJlIHdoZXJlIHlvdXIgQ2hyaXN0bWFzIHNob3BwaW5nIGlzIG1vcmUgbHV4dXJpb3VzIHRoYW4gZXZlciE8XC9wPlxyXG5cclxuPHA+VGhlIGN5Y2xlIGdyYXBoLCBDPHN1Yj5uPFwvc3ViPiwgbiAmZ2U7IDMsIGlzIGEgc2ltcGxlIHVuZGlyZWN0ZWQgZ3JhcGgsIG9uIHZlcnRleCBzZXQgezEsLi4uLG59LCB3aXRoIGVkZ2Ugc2V0IEUoQzxzdWI+bjxcL3N1Yj4pID0ge3thLGJ9IHwgfGEtYnwgJmVxdWl2OyAxIG1vZCBufS4gSXQgaXMgMi1yZWd1bGFyLCBhbmQgY29udGFpbnMgbiBlZGdlcy4gVGhlIGdyYXBocyBDPHN1Yj4zPFwvc3ViPiwgQzxzdWI+NDxcL3N1Yj4sIEM8c3ViPjU8XC9zdWI+LCBhbmQgQzxzdWI+NjxcL3N1Yj4gYXJlIGRlcGljdGVkIGluIEZpZ3VyZSAxLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2MxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2N3B4OyB3aWR0aDo2MjdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMTogVGhlIGdyYXBocyBDPHN1Yj4zPFwvc3ViPiwgQzxzdWI+NDxcL3N1Yj4sIEM8c3ViPjU8XC9zdWI+LCBhbmQgQzxzdWI+NjxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPllvdXIgXHVmYjAxcnN0IHN0ZXAgdG93YXJkcyBOb2JlbCBQcml6ZSBmYW1lIGlzIHRvIGJlIGFibGUgdG8gY29tcHV0ZSB0aGUgbnVtYmVyIG9mIG1hdGNoaW5ncyBpbiZuYnNwO3RoZSBjeWNsZSBncmFwaCBDPHN1Yj5uPFwvc3ViPi4gSW4gRmlndXJlIDIgdGhlIHNldmVuIG1hdGNoaW5ncyBvZiB0aGUgZ3JhcGggQzxzdWI+NDxcL3N1Yj4gYXJlIGRlcGljdGVkLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2MyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjExN3B4OyB3aWR0aDo2MTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMjogVGhlIG1hdGNoaW5ncyBvZiBDPHN1Yj40PFwvc3ViPi4gVGhlIGVkZ2VzIHRoYXQgYXJlIHBhcnQgb2YgdGhlIHJlc3BlY3RpdmUgbWF0Y2hpbmcgYXJlIGNvbG91cmVkIGdyZWVuLCB3aGlsZSB0aGUgZWRnZXMgbGVmdCBvdXQgb2YgdGhlIG1hdGNoaW5nIGFyZSBkYXNoZWQuIE08c3ViPjE8XC9zdWI+ID0gJmVtcHR5OywgTTxzdWI+MjxcL3N1Yj4gPSB7ezIsMX19LCBNPHN1Yj4zPFwvc3ViPiA9IHt7MywyfX0sIE08c3ViPjQ8XC9zdWI+ID0ge3s0LDN9fSwgTTxzdWI+NTxcL3N1Yj4gPSB7ezEsNH19LCBNPHN1Yj42PFwvc3ViPiA9IHt7MiwxfSx7NCwzfX0sIGFuZCBNPHN1Yj43PFwvc3ViPiA9IHt7MywyfSx7MSw0fX0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHlvdSBnZXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyOiBuLCB3aXRoIDMgJmxlOyBuICZsZTsgMTAwMDA8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGEgcm93IGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBtYXRjaGluZ3MgaW4gQzxzdWI+bjxcL3N1Yj4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d