시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 512 MB 449 302 238 69.795%

문제

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
W3sicHJvYmxlbV9pZCI6IjE3NTIwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQmFsYW5jZWQgU3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD4wXHVhY2ZjIDFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgMDEwMTEwMVx1Yzc0MCAwXHVhY2ZjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCAxIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHViZmQwXHViOWNjIFx1YzU0NFx1YjJjOFx1Yjc3YywgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IDAsIDAxLCAwMTAsIDAxMDEsIDAxMDExLCAwMTAxMTAsIDAxMDExMDEgXHViYWE4XHViNDUwIDBcdWFjZmMgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIDEgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0LCBcdWM3NzRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggMFx1YWNmYyAxXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgMVx1Yzc3NFx1ZDU1OFx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgPHN0cm9uZz5cdWFkZTBcdWQ2MTVcdWM3YTFcdWQ3OGMgXHViYjM4XHVjNzkwXHVjNWY0PFwvc3Ryb25nPlx1Yzc3NFx1Yjc3YyBcdWJkODBcdWI5NzhcdWIyZTQuIFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM3OTBcdWNjYjRcdWIzYzQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggPGVtPm48XC9lbT4gXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMsIFx1YWUzOFx1Yzc3NFx1YWMwMCA8ZW0+bjxcL2VtPiBcdWM3NzggXHVjNzc0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhZGUwXHVkNjE1XHVjN2ExXHVkNzhjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIDxlbT5uPFwvZW0+ID0gM1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMDEwLCAwMTEsIDEwMCwgMTAxIFx1YjEyNCBcdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YWRlMFx1ZDYxNVx1YzdhMVx1ZDc4YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwXHVjNzg1XHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCA8ZW0+bjxcL2VtPiAoMSAmbGU7IDxlbT5uPFwvZW0+ICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWQ0NWNcdWM5MDBcdWNkOWNcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWFlMzhcdWM3NzRcdWFjMDAgPGVtPm48XC9lbT4gXHVjNzc4IFx1Yzc3NFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWRlMFx1ZDYxNVx1YzdhMVx1ZDc4YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIDE2NzY5MDIzXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzAgXHVhYzEyXHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3NTIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmFsYW5jZWQgU3RyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBudW1iZXIgb2YgMCZwcmltZTtzIGFuZCB0aGUgbnVtYmVyIG9mIDEmcHJpbWU7cyBvZiBhIGJpbmFyeSBzdHJpbmcgMDEwMTEwMSBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMS4gRnVydGhlcm1vcmUsIGFsbCBzdWJzdHJpbmdzIG9mIDAxMDExMDEgaW5jbHVkaW5nIHRoZSBmaXJzdCBjaGFyYWN0ZXIsIGkuZS4gMCwgMDEsIDAxMCwgMDEwMSwgMDEwMTEsIDAxMDExMCwgYW5kIDAxMDExMDEgaGF2ZSB0aGUgZGlmZmVyZW5jZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMS48XC9wPlxyXG5cclxuPHA+QSBiaW5hcnkgc3RyaW5nIDxlbT5TPFwvZW0+IGlzIGNvbnNpZGVyZWQgYSA8c3Ryb25nPmJhbGFuY2VkIHN0cmluZzxcL3N0cm9uZz4gaWYgdGhlIGRpZmZlcmVuY2Ugb2YgdGhlIG51bWJlciBvZiAwIGFuZCB0aGUgbnVtYmVyIG9mIDEgaXMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEgZm9yIGFsbCBzdWJzdHJpbmdzIG9mIDxlbT5TPFwvZW0+IHRoYXQgaW5jbHVkZSB0aGUgZmlyc3QgY2hhcmFjdGVyLiBOb3RlIHRoYXQgPGVtPlM8XC9lbT4gaXRzZWxmIGlzIGEgc3Vic3RyaW5nIG9mIDxlbT5TPFwvZW0+LjxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHBvc2l0aXZlIGludGVnZXIgPGVtPm48XC9lbT4sIHdyaXRlIGEgcHJvZ3JhbSB0byBmaW5kIHRoZSBudW1iZXIgb2YgYmFsYW5jZWQgc3RyaW5ncyBmb3IgdGhlIHN0cmluZ3Mgb2YgdGhlIGxlbmd0aCA8ZW0+bjxcL2VtPi48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIDxlbT5uPFwvZW0+ID0gMywgZm91ciBzdHJpbmdzLCAwMTAsIDAxMSwgMTAwLCAxMDEsIGFyZSBiYWxhbmNlZCBzdHJpbmdzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgPGVtPm48XC9lbT4gKDEgJmxlOyA8ZW0+bjxcL2VtPiAmbGU7IDEwMCwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIDxlbT5CPFwvZW0+IG1vZHVsbyAxNjc2OTAyMyB3aGVyZSA8ZW0+QjxcL2VtPiZuYnNwO2lzIHRoZSBudW1iZXIgb2YgYmFsYW5jZWQgc3RyaW5ncyBvZiBsZW5ndGggPGVtPm48XC9lbT4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d