CF149E Martian Strings

During the study of the Martians Petya clearly understood that the Martians are absolutely lazy. They like to sleep and don't like to wake up. Imagine a Martian who has exactly $ n $ eyes located in a row and numbered from the left to the right from $ 1 $ to $ n $ . When a Martian sleeps, he puts a patch on each eye (so that the Martian morning doesn't wake him up). The inner side of each patch has an uppercase Latin letter. So, when a Martian wakes up and opens all his eyes he sees a string $ s $ consisting of uppercase Latin letters. The string's length is $ n $ . "Ding dong!" — the alarm goes off. A Martian has already woken up but he hasn't opened any of his eyes. He feels that today is going to be a hard day, so he wants to open his eyes and see something good. The Martian considers only $ m $ Martian words beautiful. Besides, it is hard for him to open all eyes at once so early in the morning. So he opens two non-overlapping segments of consecutive eyes. More formally, the Martian chooses four numbers $ a $ , $ b $ , $ c $ , $ d $ , ( $ 1

The first line contains a non-empty string $ s $ consisting of uppercase Latin letters. The strings' length is $ n $ ( $ 2

Print the single integer — the number of different beautiful strings the Martian can see this morning.

由 ChatGPT 5 翻译