시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 38 16 14 41.176%

문제

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

문자열 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+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWI3ODAsIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBpXHViYzg4XHVjOWY4XHViZDgwXHVkMTMwIGpcdWJjODhcdWM5ZjhcdWFlNGNcdWM5YzAgXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0LiAoMSAmbGU7IGkgJmxlOyBqICZsZTsgbikgXHVjNzc0XHViNTRjLCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YWMxOVx1YjM1NFx1Yjc3Y1x1YjNjNCAoaSwgailcdWFjMDAgXHViMmU0XHViOTc0XHViMmU0XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWJkODBcdWJkODQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD54PHN1Yj4xPFwvc3ViPix4PHN1Yj4yPFwvc3ViPiwuLi4seDxzdWI+bDxcL3N1Yj5cdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWJhYThcdWI0ZTAgXHVjNzA0XHVjZTU4IGlcdWM1ZDBcdWMxMWMgeDxzdWI+aTxcL3N1Yj4gPSB4PHN1Yj5sLWkrMTxcL3N1Yj5cdWM3NDQgXHViOWNjXHVjODcxXHVkNTYwIFx1YjU0YywgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgKCYjMzk7YSYjMzk7LSYjMzk7eiYjMzk7LCAmIzM5O0EmIzM5Oy0mIzM5O1omIzM5OykgXHViMzAwXHViYjM4XHVjNzkwXHVjNjQwIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1YjI5NCBcdWIyZTRcdWI5NzggXHViYjM4XHVjNzkwXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIChBXHVjNjQwIGFcdWIyOTQgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YjJlNCk8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgU1x1Yzc1OCBcdWQwNmNcdWFlMzAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbiAmbGU7IDMmbWlkZG90OzEwPHN1cD41PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5TXHVjNzU4IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjQgXHVjOTExLCBcdWQ1NThcdWM3NzRcdWQzN2NcdWI0ZGNcdWI4NmNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjY2FiIFx1YmM4OFx1Y2EzMCBcdWM2MDhcdWM4MWNcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwIDZcdWFjMWNcdWM3NTggXHVkNTU4XHVjNzc0XHVkMzdjXHViNGRjXHViODZjXHVjNzc0IFx1Yzc4OFx1YjJlNC4gLSZuYnNwOygxLCAxKSwgKDEsIDIpLCAoMSwgMyksICgyLCAyKSwgKDIsIDMpLCAoMywgMykuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAxMlx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuIC0gKDEsIDEpLCAoMiwgMiksICgzLCAzKSwgKDQsIDQpLCAoNSwgNSksICg2LCA2KSwgKDcsIDcpLCAoMSwgMyksICgzLCA1KSwgKDUsIDcpLCAoMiwgNiksICgxLCA3KTxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgNVx1YWMxY1x1Yzc1OCBcdWQ1NThcdWM3NzRcdWQzN2NcdWI0ZGNcdWI4NmMgXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gLSAoMSwgMSksICgxLCAzKSwgKDIsIDIpLCAoMiwgMyksICgzLCA0KS4gXHViZDgwXHViZDg0XHViYjM4XHVjNzkwXHVjNWY0ICgxLCAzKSAmcXVvdDthQUEmcXVvdDsgXHViMjk0IFx1ZDU1OFx1Yzc3NFx1ZDM3Y1x1YjRkY1x1Yjg2Y1x1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjNTQ0XHViMmM4XHVjOWMwXHViOWNjLCBcdWM3YWNcdWJjMzBcdWM1ZjRcdWQ1NzRcdWMxMWMgJnF1b3Q7QWFBJnF1b3Q7XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5OTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIeXBlcmRyb21lIiwiZGVzY3JpcHRpb24iOiI8cD5IeXBlcmdub21lIHBsYW5ldCBpcyBmYW1vdXMgZm9yIGl0cyBHcmVhdCBVbml2ZXJzYWwgR2FtZXMgYmV0d2VlbiBnbm9tZXMgJm1kYXNoOyB0aGUgR2FtZXMgYmV0d2VlbiBnbm9tZXMgZnJvbSBlYWNoIHBhcnQgb2YgdGhlIGdhbGF4eSBpbiB2YXJpb3VzIGRpc2NpcGxpbmVzLjxcL3A+XHJcblxyXG48cD5UaGUgbW9zdCBwb3B1bGFyIGRpc2NpcGxpbmUgaW4gdGhlIEdhbWVzIGlzIHRoZSBIeXBlcmRyb21lIGRpc2NpcGxpbmUuIFRoZSBydWxlcyBhcmUgdGhlIGZvbGxvd3M6IG9uZSBzdHJpbmcgb2YgbGVuZ3RoIG4gaXMgZ2l2ZW4gdG8gYWxsIGdub21lcy4gVGhlIGdub21lcyBzaGFsbCBcdWZiMDFuZCwgYXMgZmFzdCBhcyB0aGV5IGNhbiwgdGhlIHRvdGFsIG51bWJlciBvZiBIeXBlcmRyb21lIHN1YnN0cmluZ3MgJm1kYXNoOyBzdWNoIHN0cmluZ3MgdGhhdCBjaGFyYWN0ZXJzIGluc2lkZSB0aGUgc3RyaW5nIGNhbiBiZSByZWFycmFuZ2VkIHRvIGdldCBhIHBhbGluZHJvbWUuPFwvcD5cclxuXHJcbjxwPlN1YnN0cmluZyBpcyBkZVx1ZmIwMW5lZCBhcyBhIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMgZnJvbSBwb3NpdGlvbiBpIHRvIHBvc2l0aW9uIGogaW5jbHVzaXZlLCB3aGVyZSAxICZsZTsgaSAmbGU7IGogJmxlOyBuLiBTdWJzdHJpbmdzIHdpdGggZGlcdWZiMDBlcmVudCBwYWlycyBvZiBwb3NpdGlvbnMgKGksIGopIGFyZSBjb25zaWRlcmVkIGRpXHVmYjAwZXJlbnQgcmVnYXJkbGVzcyBvZiB0aGVpciBjb250ZW50cy48XC9wPlxyXG5cclxuPHA+UGFsaW5kcm9tZSBpcyBkZVx1ZmIwMW5lZCBhcyBhIHN0cmluZyB4PHN1Yj4xPFwvc3ViPng8c3ViPjI8XC9zdWI+Li4ueDxzdWI+bDxcL3N1Yj4gLCB3aGVyZSB4PHN1Yj5pPFwvc3ViPiA9IHg8c3ViPmw8XC9zdWI+Jm1pbnVzO2krMSBmb3IgYWxsIDEgJmxlOyBpICZsZTsgbC48XC9wPlxyXG5cclxuPHA+SnVkZ2VzIGNob29zZSBhIHN0cmluZyBhbmQgeW91ciB0YXNrIGlzIHRvIGhlbHAgdGhlbSBcdWZiMDFuZCB0aGUgYW5zd2VyLjxcL3A+XHJcblxyXG48cD5UaGUgZ25vbWUgYWxwaGFiZXQgY29uc2lzdHMgb2YgbG93ZXJjYXNlIGFuZCB1cHBlcmNhc2UgRW5nbGlzaCBsZXR0ZXJzICZtZGFzaDsgJmxzcXVvO2EmcnNxdW87Jm5kYXNoOyZsc3F1bzt6JnJzcXVvOyBhbmQgJmxzcXVvO0EmcnNxdW87Jm5kYXNoOyZsc3F1bztaJnJzcXVvOyB3aGVyZSBsZXR0ZXJzIGluIGRpXHVmYjAwZXJlbnQgY2FzZSBhcmUgY29uc2lkZXJlZCB0byBiZSBkaVx1ZmIwMGVyZW50IGxldHRlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAzJm1pZGRvdDsxMDxzdXA+NTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiB0aGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgdGhlIHN0cmluZyBmb3IgSHlwZXJkcm9tZSBkaXNjaXBsaW5lICZtZGFzaDsgbiBsb3dlcmNhc2Ugb3IgdXBwZXJjYXNlIEVuZ2xpc2ggbGV0dGVycy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGFuc3dlciBmb3IgdGhlIEh5cGVyZHJvbWUgZGlzY2lwbGluZSAmbWRhc2g7IHRoZSBudW1iZXIgb2YgSHlwZXJkcm9tZSBzdWJzdHJpbmdzIGluIHRoZSBpbnB1dCBzdHJpbmcuPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCBleGFtcGxlIHRoZXJlIGFyZSA2IEh5cGVyZHJvbWUgc3Vic3RyaW5ncyAmbWRhc2g7ICgxLCAxKSwgKDEsIDIpLCAoMSwgMyksICgyLCAyKSwgKDIsIDMpLCAoMywgMykuPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgZXhhbXBsZSB0aGVyZSBhcmUgMTIgSHlwZXJkcm9tZSBzdWJzdHJpbmdzICZtZGFzaDsgKDEsIDEpLCAoMiwgMiksICgzLCAzKSwgKDQsIDQpLCAoNSwgNSksICg2LCA2KSwgKDcsIDcpLCAoMSwgMyksICgzLCA1KSwgKDUsIDcpLCAoMiwgNiksICgxLCA3KS48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHRoaXJkIGV4YW1wbGUgdGhlcmUgYXJlIDUgSHlwZXJkcm9tZSBzdWJzdHJpbmdzICZtZGFzaDsgKDEsIDEpLCAoMSwgMyksICgyLCAyKSwgKDIsIDMpLCAoMywgMykuIE5vdGUsIHRoYXQgYSBIeXBlcmRyb21lIHN1YnN0cmluZyAoMSwgMykgaXMgJmxkcXVvO2FBQSZyZHF1bzsuIEl0IGlzIG5vdCBhIHBhbGluZHJvbWUgaXRzZWxmLCBidXQgaXRzIGNoYXJhY3RlcnMgY2FuIGJlIHJlYXJyYW5nZWQgdG8gZ2V0IGEgcGFsaW5kcm9tZSAmbGRxdW87QWFBJnJkcXVvOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d