시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 512 MB 297 203 156 70.909%

문제

0과 1로 이루어진 이진 문자열 0101101은 0과 1의 개수의 차이가 1 이하이다. 뿐만 아니라, 첫번째 문자를 포함하는 모든 부분 문자열 0, 01, 010, 0101, 01011, 010110, 0101101 모두 0과 1의 개수의 차이가 1 이하이다.

이와 같이, 이진 문자열 중에서 첫번째 문자를 포함하는 모든 부분 문자열의 0과 1의 개수의 차이가 1이하인 문자열을 균형잡힌 문자열이라 부른다. 문자열 자체도 자신의 부분 문자열이다.

양의 정수 n 이 주어질 때, 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 수를 구하는 프로그램을 작성하시오.

예를 들어, n = 3인 경우에는 010, 011, 100, 101 네 개의 문자열이 균형잡힌 문자열이다.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다.

출력

출력은 표준출력을 사용한다. 길이가 n 인 이진 문자열 중에서 균형잡힌 문자열의 개수를 16769023로 나눈 나머지 값을 한 줄에 출력한다.

예제 입력 1

3

예제 출력 1

4

예제 입력 2

22

예제 출력 2

2048

예제 입력 3

101

예제 출력 3

393256
W3sicHJvYmxlbV9pZCI6IjE3NTIwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQmFsYW5jZWQgU3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD4wXHVhY2ZjIDFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgMDEwMTEwMVx1Yzc0MCAwXHVhY2ZjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCAxIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHViZmQwXHViOWNjIFx1YzU0NFx1YjJjOFx1Yjc3YywgXHVjY2FiXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgMCwgMDEsIDAxMCwgMDEwMSwgMDEwMTEsIDAxMDExMCwgMDEwMTEwMSBcdWJhYThcdWI0NTAgMFx1YWNmYyAxXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgMSBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NzQsIFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IDBcdWFjZmMgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIDFcdWM3NzRcdWQ1NThcdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IDxzdHJvbmc+XHVhZGUwXHVkNjE1XHVjN2ExXHVkNzhjIFx1YmIzOFx1Yzc5MFx1YzVmNDxcL3N0cm9uZz5cdWM3NzRcdWI3N2MgXHViZDgwXHViOTc4XHViMmU0LiBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjNzkwXHVjY2I0XHViM2M0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IDxlbT5uPFwvZW0+IFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWFlMzhcdWM3NzRcdWFjMDAgPGVtPm48XC9lbT4gXHVjNzc4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWRlMFx1ZDYxNVx1YzdhMVx1ZDc4YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA8ZW0+bjxcL2VtPiA9IDNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDAxMCwgMDExLCAxMDAsIDEwMSBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWFkZTBcdWQ2MTVcdWM3YTFcdWQ3OGMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Yzc4NVx1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggPGVtPm48XC9lbT4gKDEgJmxlOyA8ZW0+bjxcL2VtPiAmbGU7IDEwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjZDljXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVhZTM4XHVjNzc0XHVhYzAwIDxlbT5uPFwvZW0+IFx1Yzc3OCBcdWM3NzRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFkZTBcdWQ2MTVcdWM3YTFcdWQ3OGMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxNjc2OTAyM1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwIFx1YWMxMlx1Yzc0NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzUyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJhbGFuY2VkIFN0cmluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgbnVtYmVyIG9mIDAmcHJpbWU7cyBhbmQgdGhlIG51bWJlciBvZiAxJnByaW1lO3Mgb2YgYSBiaW5hcnkgc3RyaW5nIDAxMDExMDEgaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEuIEZ1cnRoZXJtb3JlLCBhbGwgc3Vic3RyaW5ncyBvZiAwMTAxMTAxIGluY2x1ZGluZyB0aGUgZmlyc3QgY2hhcmFjdGVyLCBpLmUuIDAsIDAxLCAwMTAsIDAxMDEsIDAxMDExLCAwMTAxMTAsIGFuZCAwMTAxMTAxIGhhdmUgdGhlIGRpZmZlcmVuY2UgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEuPFwvcD5cclxuXHJcbjxwPkEgYmluYXJ5IHN0cmluZyA8ZW0+UzxcL2VtPiBpcyBjb25zaWRlcmVkIGEgPHN0cm9uZz5iYWxhbmNlZCBzdHJpbmc8XC9zdHJvbmc+IGlmIHRoZSBkaWZmZXJlbmNlIG9mIHRoZSBudW1iZXIgb2YgMCBhbmQgdGhlIG51bWJlciBvZiAxIGlzIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxIGZvciBhbGwgc3Vic3RyaW5ncyBvZiA8ZW0+UzxcL2VtPiB0aGF0IGluY2x1ZGUgdGhlIGZpcnN0IGNoYXJhY3Rlci4gTm90ZSB0aGF0IDxlbT5TPFwvZW0+IGl0c2VsZiBpcyBhIHN1YnN0cmluZyBvZiA8ZW0+UzxcL2VtPi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwb3NpdGl2ZSBpbnRlZ2VyIDxlbT5uPFwvZW0+LCB3cml0ZSBhIHByb2dyYW0gdG8gZmluZCB0aGUgbnVtYmVyIG9mIGJhbGFuY2VkIHN0cmluZ3MgZm9yIHRoZSBzdHJpbmdzIG9mIHRoZSBsZW5ndGggPGVtPm48XC9lbT4uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiA8ZW0+bjxcL2VtPiA9IDMsIGZvdXIgc3RyaW5ncywgMDEwLCAwMTEsIDEwMCwgMTAxLCBhcmUgYmFsYW5jZWQgc3RyaW5ncy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIDxlbT5uPFwvZW0+ICgxICZsZTsgPGVtPm48XC9lbT4gJmxlOyAxMDAsMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiA8ZW0+QjxcL2VtPiBtb2R1bG8gMTY3NjkwMjMgd2hlcmUgPGVtPkI8XC9lbT4mbmJzcDtpcyB0aGUgbnVtYmVyIG9mIGJhbGFuY2VkIHN0cmluZ3Mgb2YgbGVuZ3RoIDxlbT5uPFwvZW0+LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==