시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 275 153 135 64.593%

문제

존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다.

이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 26마리고, A, B, ... Z라는 이름이 붙는다. 존은 52개의 점을 시계방향으로 보면서 각 점을 어떤 소가 지나가는지 기록했다. 이렇게 만들어 낸 52글자의 문자열에는 각 알파벳이 두 번씩 나타날 것이다.

어떤 두 소는 어떤 방법으로 걷든 그 경로가 어딘가에서 만나야 될 수도 있다. 그런 소가 총 몇 쌍인지 구해 보자.

입력

첫 줄에 52글자의 문자열이 주어진다. 각 글자는 알파벳 대문자이며, 각 알파벳이 정확히 두 번씩 나타난다.

출력

경로가 무조건 만나는 소가 몇 쌍인지 출력한다.

예제 입력 1

ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ

예제 출력 1

1

힌트

A와 B의 경로는 무조건 만난다.

W3sicHJvYmxlbV9pZCI6IjE0NDY4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTVcdWM1ZDBcdWIyOTQgXHVjNmQwXHVkNjE1IFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YWRmOCBcdWI0NThcdWI4MDhcdWM1ZDAgXHVhZTM4XHVjNzc0IFx1YjQ1OFx1YjdlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzg3NFx1Yzc1OCBcdWMxOGNcdWIyOTQgXHViOWU0XHVjNzdjIFx1YzU0NFx1Y2U2OCBcdWM3NzQgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YWMwMCBcdWQ0ODBcdWM3NDQgXHViYTM5XHVhY2UwIFx1YzgwMFx1YjE0MVx1YzVkMCBcdWIyZTRcdWMyZGMgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwOFx1YWMwMCBcdWQ1ZGJcdWFjMDRcdWM3M2NcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjMThjXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWMyYjVcdWFkMDBcdWIzMDBcdWI4NWMgXHViOWU0XHVjNzdjIFx1YjYxMVx1YWMxOVx1Yzc0MCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVhZTM4XHVjNzQ0IFx1YWM3NFx1YjEwY1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzE4Y1x1YjI5NCBcdWM2ZDBcdWQ2MTUgXHVhZTM4XHVjNzU4IFx1YzgxNVx1ZDU3NFx1YzljNCBcdWQ1NWMgXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWM4MTBcdWM3NDQgXHVjOWMwXHViMDk4IFx1YjA5OFx1YWMwNFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWMxOGNcdWIzYzQgXHVhZTM4IFx1YzcwNFx1Yzc1OCBcdWFjMTlcdWM3NDAgXHVjODEwXHVjNzQ0IFx1YzljMFx1YjA5OFx1YWMwMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YWM3OCBcdWM5YzBcdWNmMWNcdWJjZjggXHVjODc0XHVjNzQwIFx1Yzc3NCBcdWM4MTBcdWI0ZTRcdWM3NDQgXHViZDg0XHVjMTFkXHVkNTc0IFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzE4Y1x1YjI5NCBcdWNkMWQgMjZcdWI5YzhcdWI5YWNcdWFjZTAsIEEsIEIsIC4uLiBaXHViNzdjXHViMjk0IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWJkOTlcdWIyOTRcdWIyZTQuIFx1Yzg3NFx1Yzc0MCA1Mlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NDQgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmNmNFx1YmE3NFx1YzExYyBcdWFjMDEgXHVjODEwXHVjNzQ0IFx1YzViNFx1YjVhNCBcdWMxOGNcdWFjMDAgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0XHVjOWMwIFx1YWUzMFx1Yjg1ZFx1ZDU4OFx1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNCBcdWIwYjggNTJcdWFlMDBcdWM3OTBcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzQgXHViNDUwIFx1YmM4OFx1YzUyOSBcdWIwOThcdWQwYzBcdWIwYTAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgXHViNDUwIFx1YzE4Y1x1YjI5NCBcdWM1YjRcdWI1YTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM3N1x1YjRlMCBcdWFkZjggXHVhY2JkXHViODVjXHVhYzAwIFx1YzViNFx1YjUxOFx1YWMwMFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWM1N2MgXHViNDIwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWMxOGNcdWFjMDAgXHVjZDFkIFx1YmE4NyBcdWMzMGRcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTc0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgNTJcdWFlMDBcdWM3OTBcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHVjNzc0XHViYTcwLCBcdWFjMDEgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWI0NTAgXHViYzg4XHVjNTI5IFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjYmRcdWI4NWNcdWFjMDAgXHViYjM0XHVjODcwXHVhYzc0IFx1YjljY1x1YjA5OFx1YjI5NCBcdWMxOGNcdWFjMDAgXHViYTg3IFx1YzMwZFx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPkFcdWM2NDAgQlx1Yzc1OCBcdWFjYmRcdWI4NWNcdWIyOTQgXHViYjM0XHVjODcwXHVhYzc0IFx1YjljY1x1YjA5Y1x1YjJlNC48YnI+PFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDY4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2h5IERpZCB0aGUgQ293IENyb3NzIHRoZSBSb2FkIElJIChCcm9uemUpIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgbGF5b3V0IG9mIEZhcm1lciBKb2huJiMzOTtzIGZhcm0gaXMgcXVpdGUgcGVjdWxpYXIsIHdpdGggYSBsYXJnZSBjaXJjdWxhciByb2FkIHJ1bm5pbmcgYXJvdW5kIHRoZSBwZXJpbWV0ZXIgb2YgdGhlIG1haW4gZmllbGQgb24gd2hpY2ggaGlzIGNvd3MgZ3JhemUgZHVyaW5nIHRoZSBkYXkuIEV2ZXJ5IG1vcm5pbmcsIHRoZSBjb3dzIGNyb3NzIHRoaXMgcm9hZCBvbiB0aGVpciB3YXkgdG93YXJkcyB0aGUgZmllbGQsIGFuZCBldmVyeSBldmVuaW5nIHRoZXkgYWxsIGNyb3NzIGFnYWluIGFzIHRoZXkgbGVhdmUgdGhlIGZpZWxkIGFuZCByZXR1cm4gdG8gdGhlIGJhcm4uPFwvcD5cclxuXHJcbjxwPkFzIHdlIGtub3csIGNvd3MgYXJlIGNyZWF0dXJlcyBvZiBoYWJpdCwgYW5kIHRoZXkgZWFjaCBjcm9zcyB0aGUgcm9hZCB0aGUgc2FtZSB3YXkgZXZlcnkgZGF5LiBFYWNoIGNvdyBjcm9zc2VzIGludG8gdGhlIGZpZWxkIGF0IGEgZGlmZmVyZW50IHBvaW50IGZyb20gd2hlcmUgc2hlIGNyb3NzZXMgb3V0IG9mIHRoZSBmaWVsZCwgYW5kIGFsbCBvZiB0aGVzZSBjcm9zc2luZyBwb2ludHMgYXJlIGRpc3RpbmN0IGZyb20gZWFjaC1vdGhlci4gRmFybWVyIEpvaG4gb3ducyBleGFjdGx5IDI2IGNvd3MsIHdoaWNoIGhlIGhhcyBsYXppbHkgbmFtZWQgQSB0aHJvdWdoIFogKGhlIGlzIG5vdCBzdXJlIHdoYXQgaGUgd2lsbCBkbyBpZiBoZSBldmVyIGFjcXVpcmVzIGEgMjd0aCBjb3cuLi4pLCBzbyB0aGVyZSBhcmUgcHJlY2lzZWx5IDUyIGNyb3NzaW5nIHBvaW50cyBhcm91bmQgdGhlIHJvYWQuIEZhcm1lciBKb2huIHJlY29yZHMgdGhlc2UgY3Jvc3NpbmcgcG9pbnRzIGNvbmNpc2VseSBieSBzY2FubmluZyBhcm91bmQgdGhlIGNpcmNsZSBjbG9ja3dpc2UsIHdyaXRpbmcgZG93biB0aGUgbmFtZSBvZiB0aGUgY293IGZvciBlYWNoIGNyb3NzaW5nIHBvaW50LCB1bHRpbWF0ZWx5IGZvcm1pbmcgYSBzdHJpbmcgd2l0aCA1MiBjaGFyYWN0ZXJzIGluIHdoaWNoIGVhY2ggbGV0dGVyIG9mIHRoZSBhbHBoYWJldCBhcHBlYXJzIGV4YWN0bHkgdHdpY2UuIEhlIGRvZXMgbm90IHJlY29yZCB3aGljaCBjcm9zc2luZyBwb2ludHMgYXJlIGVudHJ5IHBvaW50cyBhbmQgd2hpY2ggYXJlIGV4aXQgcG9pbnRzLjxcL3A+XHJcblxyXG48cD5Mb29raW5nIGF0IGhpcyBtYXAgb2YgY3Jvc3NpbmcgcG9pbnRzLCBGYXJtZXIgSm9obiBpcyBjdXJpb3VzIGhvdyBtYW55IHRpbWVzIHZhcmlvdXMgcGFpcnMgb2YgY293cyBtaWdodCBjcm9zcyBwYXRocyBkdXJpbmcgdGhlIGRheS4gSGUgY2FsbHMgYSBwYWlyIG9mIGNvd3MmbmJzcDsoYSxiKSBhICZxdW90O2Nyb3NzaW5nJnF1b3Q7IHBhaXIgaWYgY293Jm5ic3A7YSYjMzk7cyBwYXRoIGZyb20gZW50cnkgdG8gZXhpdCBtdXN0IGNyb3NzIGNvdyZuYnNwO2ImIzM5O3MgcGF0aCBmcm9tIGVudHJ5IHRvIGV4aXQuIFBsZWFzZSBoZWxwIEZhcm1lciBKb2huIGNvdW50IHRoZSB0b3RhbCBudW1iZXIgb2YgY3Jvc3NpbmcgcGFpcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIGEgc3RyaW5nIG9mIDUyIHVwcGVyLWNhc2UgY2hhcmFjdGVycy4gRWFjaCBsZXR0ZXIgb2YgdGhlIGFscGhhYmV0IGFwcGVhcnMgZXhhY3RseSB0d2ljZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2UgcHJpbnQgdGhlIHRvdGFsIG51bWJlciBvZiBjcm9zc2luZyBwYWlycy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoaXMgZXhhbXBsZSwgb25seSBjb3dzIEEgYW5kIEIgYXJlIGEgY3Jvc3NpbmcgcGFpci48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=