시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 29 15 13 52.000%

문제

문자열이 주어졌을 때, 이 문자열에 포함된 문자의 위치를 적절히 바꿔서 팰린드롬으로 만들 수 있을 때, 그 문자열을 하이퍼드롬이라고 한다.

문자열 S가 주어졌을 때, 그 문자열의 부분 문자열 중 하이퍼드롬의 개수를 구하는 프로그램을 작성하시오.

문자열의 부분 문자열이란, 문자열의 i번째부터 j번째까지 문자로 이루어진 문자열을 말한다. (1 ≤ i ≤ j ≤ n) 이 때, 부분 문자열이 같더라도 (i, j)가 다르다면 다른 부분 문자열이다.

x1,x2,...,xl로 이루어진 문자열이 모든 위치 i에서 xi = xl-i+1을 만족할 때, 팰린드롬이라고 한다.

문자열은 알파벳 대소문자로 이루어져 있고, ('a'-'z', 'A'-'Z') 대문자와 소문자는 다른 문자로 생각하면 된다. (A와 a는 다른 문자다)

입력

첫째 줄에 S의 크기 n이 주어진다. (1 ≤ n ≤ 3·105)

둘째 줄에는 S가 주어진다.

출력

S의 부분 문자열 중, 하이퍼드롬의 개수를 출력한다.

예제 입력 1

3
aaa

예제 출력 1

6

예제 입력 2

7
abadaba

예제 출력 2

12

예제 입력 3

3
aAA

예제 출력 3

5

힌트

첫 번쨰 예제의 경우에 6개의 하이퍼드롬이 있다. - (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

두 번째 예제의 경우에는 12개가 있다. - (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (1, 3), (3, 5), (5, 7), (2, 6), (1, 7)

세 번째 예제의 경우에는 5개의 하이퍼드롬 부분문자열이 있다. - (1, 1), (1, 3), (2, 2), (2, 3), (3, 4). 부분문자열 (1, 3) "aAA" 는 하이퍼드롬이다. 이 문자열은 팰린드롬이 아니지만, 재배열해서 "AaA"를 만들 수 있기 때문이다.

W3sicHJvYmxlbV9pZCI6IjM5OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NThcdWM3NzRcdWQzN2NcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWJiMzhcdWM3OTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjJm5ic3A7XHVjODAxXHVjODA4XHVkNzg4IFx1YmMxNFx1YWZkNFx1YzExYyBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1ZDU1OFx1Yzc3NFx1ZDM3Y1x1YjRkY1x1Yjg2Y1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTEgXHVkNTU4XHVjNzc0XHVkMzdjXHViNGRjXHViODZjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3ODAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBpXHViYzg4XHVjOWY4XHViZDgwXHVkMTMwIGpcdWJjODhcdWM5ZjhcdWFlNGNcdWM5YzAgXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiAoMSAmbGU7IGkgJmxlOyBqICZsZTsgbikgXHVjNzc0IFx1YjU0YywgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWFjMTlcdWIzNTRcdWI3N2NcdWIzYzQgKGksIGopXHVhYzAwIFx1YjJlNFx1Yjk3NFx1YjJlNFx1YmE3NCBcdWIyZTRcdWI5NzggXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+eDxzdWI+MTxcL3N1Yj4seDxzdWI+MjxcL3N1Yj4sLi4uLHg8c3ViPmw8XC9zdWI+XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHViYWE4XHViNGUwIFx1YzcwNFx1Y2U1OCBpXHVjNWQwXHVjMTFjIHg8c3ViPmk8XC9zdWI+ID0geDxzdWI+bC1pKzE8XC9zdWI+XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMsIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsICgmIzM5O2EmIzM5Oy0mIzM5O3omIzM5OywgJiMzOTtBJiMzOTstJiMzOTtaJiMzOTspIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWMxOGNcdWJiMzhcdWM3OTBcdWIyOTQgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiAoQVx1YzY0MCBhXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWIyZTQpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFNcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4gJmxlOyAzJm1pZGRvdDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgU1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+U1x1Yzc1OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0IFx1YzkxMSwgXHVkNTU4XHVjNzc0XHVkMzdjXHViNGRjXHViODZjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWNhMzAgXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCA2XHVhYzFjXHVjNzU4IFx1ZDU1OFx1Yzc3NFx1ZDM3Y1x1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM3ODhcdWIyZTQuIC0mbmJzcDsoMSwgMSksICgxLCAyKSwgKDEsIDMpLCAoMiwgMiksICgyLCAzKSwgKDMsIDMpLjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMTJcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0LiAtICgxLCAxKSwgKDIsIDIpLCAoMywgMyksICg0LCA0KSwgKDUsIDUpLCAoNiwgNiksICg3LCA3KSwgKDEsIDMpLCAoMywgNSksICg1LCA3KSwgKDIsIDYpLCAoMSwgNyk8XC9wPlxyXG5cclxuPHA+XHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDVcdWFjMWNcdWM3NTggXHVkNTU4XHVjNzc0XHVkMzdjXHViNGRjXHViODZjIFx1YmQ4MFx1YmQ4NFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIC0gKDEsIDEpLCAoMSwgMyksICgyLCAyKSwgKDIsIDMpLCAoMywgNCkuIFx1YmQ4MFx1YmQ4NFx1YmIzOFx1Yzc5MFx1YzVmNCAoMSwgMykgJnF1b3Q7YUFBJnF1b3Q7IFx1YjI5NCBcdWQ1NThcdWM3NzRcdWQzN2NcdWI0ZGNcdWI4NmNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YzU0NFx1YjJjOFx1YzljMFx1YjljYywgXHVjN2FjXHViYzMwXHVjNWY0XHVkNTc0XHVjMTFjICZxdW90O0FhQSZxdW90O1x1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSHlwZXJkcm9tZSIsImRlc2NyaXB0aW9uIjoiPHA+SHlwZXJnbm9tZSBwbGFuZXQgaXMgZmFtb3VzIGZvciBpdHMgR3JlYXQgVW5pdmVyc2FsIEdhbWVzIGJldHdlZW4gZ25vbWVzICZtZGFzaDsgdGhlIEdhbWVzIGJldHdlZW4gZ25vbWVzIGZyb20gZWFjaCBwYXJ0IG9mIHRoZSBnYWxheHkgaW4gdmFyaW91cyBkaXNjaXBsaW5lcy48XC9wPlxyXG5cclxuPHA+VGhlIG1vc3QgcG9wdWxhciBkaXNjaXBsaW5lIGluIHRoZSBHYW1lcyBpcyB0aGUgSHlwZXJkcm9tZSBkaXNjaXBsaW5lLiBUaGUgcnVsZXMgYXJlIHRoZSBmb2xsb3dzOiBvbmUgc3RyaW5nIG9mIGxlbmd0aCBuIGlzIGdpdmVuIHRvIGFsbCBnbm9tZXMuIFRoZSBnbm9tZXMgc2hhbGwgXHVmYjAxbmQsIGFzIGZhc3QgYXMgdGhleSBjYW4sIHRoZSB0b3RhbCBudW1iZXIgb2YgSHlwZXJkcm9tZSBzdWJzdHJpbmdzICZtZGFzaDsgc3VjaCBzdHJpbmdzIHRoYXQgY2hhcmFjdGVycyBpbnNpZGUgdGhlIHN0cmluZyBjYW4gYmUgcmVhcnJhbmdlZCB0byBnZXQgYSBwYWxpbmRyb21lLjxcL3A+XHJcblxyXG48cD5TdWJzdHJpbmcgaXMgZGVcdWZiMDFuZWQgYXMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIGZyb20gcG9zaXRpb24gaSB0byBwb3NpdGlvbiBqIGluY2x1c2l2ZSwgd2hlcmUgMSAmbGU7IGkgJmxlOyBqICZsZTsgbi4gU3Vic3RyaW5ncyB3aXRoIGRpXHVmYjAwZXJlbnQgcGFpcnMgb2YgcG9zaXRpb25zIChpLCBqKSBhcmUgY29uc2lkZXJlZCBkaVx1ZmIwMGVyZW50IHJlZ2FyZGxlc3Mgb2YgdGhlaXIgY29udGVudHMuPFwvcD5cclxuXHJcbjxwPlBhbGluZHJvbWUgaXMgZGVcdWZiMDFuZWQgYXMgYSBzdHJpbmcgeDxzdWI+MTxcL3N1Yj54PHN1Yj4yPFwvc3ViPi4uLng8c3ViPmw8XC9zdWI+ICwgd2hlcmUgeDxzdWI+aTxcL3N1Yj4gPSB4PHN1Yj5sPFwvc3ViPiZtaW51cztpKzEgZm9yIGFsbCAxICZsZTsgaSAmbGU7IGwuPFwvcD5cclxuXHJcbjxwPkp1ZGdlcyBjaG9vc2UgYSBzdHJpbmcgYW5kIHlvdXIgdGFzayBpcyB0byBoZWxwIHRoZW0gXHVmYjAxbmQgdGhlIGFuc3dlci48XC9wPlxyXG5cclxuPHA+VGhlIGdub21lIGFscGhhYmV0IGNvbnNpc3RzIG9mIGxvd2VyY2FzZSBhbmQgdXBwZXJjYXNlIEVuZ2xpc2ggbGV0dGVycyAmbWRhc2g7ICZsc3F1bzthJnJzcXVvOyZuZGFzaDsmbHNxdW87eiZyc3F1bzsgYW5kICZsc3F1bztBJnJzcXVvOyZuZGFzaDsmbHNxdW87WiZyc3F1bzsgd2hlcmUgbGV0dGVycyBpbiBkaVx1ZmIwMGVyZW50IGNhc2UgYXJlIGNvbnNpZGVyZWQgdG8gYmUgZGlcdWZiMDBlcmVudCBsZXR0ZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMyZtaWRkb3Q7MTA8c3VwPjU8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIHRoZSBzdHJpbmcgZm9yIEh5cGVyZHJvbWUgZGlzY2lwbGluZSAmbWRhc2g7IG4gbG93ZXJjYXNlIG9yIHVwcGVyY2FzZSBFbmdsaXNoIGxldHRlcnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBhbnN3ZXIgZm9yIHRoZSBIeXBlcmRyb21lIGRpc2NpcGxpbmUgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIEh5cGVyZHJvbWUgc3Vic3RyaW5ncyBpbiB0aGUgaW5wdXQgc3RyaW5nLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSB0aGVyZSBhcmUgNiBIeXBlcmRyb21lIHN1YnN0cmluZ3MgJm1kYXNoOyAoMSwgMSksICgxLCAyKSwgKDEsIDMpLCAoMiwgMiksICgyLCAzKSwgKDMsIDMpLjxcL3A+XHJcblxyXG48cD5JbiB0aGUgc2Vjb25kIGV4YW1wbGUgdGhlcmUgYXJlIDEyIEh5cGVyZHJvbWUgc3Vic3RyaW5ncyAmbWRhc2g7ICgxLCAxKSwgKDIsIDIpLCAoMywgMyksICg0LCA0KSwgKDUsIDUpLCAoNiwgNiksICg3LCA3KSwgKDEsIDMpLCAoMywgNSksICg1LCA3KSwgKDIsIDYpLCAoMSwgNykuPFwvcD5cclxuXHJcbjxwPkluIHRoZSB0aGlyZCBleGFtcGxlIHRoZXJlIGFyZSA1IEh5cGVyZHJvbWUgc3Vic3RyaW5ncyAmbWRhc2g7ICgxLCAxKSwgKDEsIDMpLCAoMiwgMiksICgyLCAzKSwgKDMsIDMpLiBOb3RlLCB0aGF0IGEgSHlwZXJkcm9tZSBzdWJzdHJpbmcgKDEsIDMpIGlzICZsZHF1bzthQUEmcmRxdW87LiBJdCBpcyBub3QgYSBwYWxpbmRyb21lIGl0c2VsZiwgYnV0IGl0cyBjaGFyYWN0ZXJzIGNhbiBiZSByZWFycmFuZ2VkIHRvIGdldCBhIHBhbGluZHJvbWUgJmxkcXVvO0FhQSZyZHF1bzs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==