409322: GYM103485 D Circular Pharaoh

The tomb of Pharaoh Tak is decorated with an insignia with a word that is his name concatenated 3 times "taktaktak". Furthermore, this word is arranged in a circular shape, so that the last letter is also neighbor to the first letter. This also happens to other Pharaohs who, like Tak, have a written word in their respective tombs that is formed as follows: while still alive, the Pharaoh writes his name once on the insignia and, after his death, his children (0 or more) write copies of their name concatenated one after the other to the end of the word. The word is then arranged in a circular shape.

Your task is given a word of an insignia, to calculate how many contiguous subsets of its letters can be the original name written by the pharaoh himself. Such a subset must comply with the restrictions described on how the word is formed. But keep in mind that since the word is circular, you don't actually even know its beginning (where the original name would begin). For example, for the word "taktaktak", there are 3 occurrences of the word "tak" and the original name can be any one of the 3 occurrences. Since the word is circular, "akt" is also a valid candidate that occurs 3 times. The word "taktaktak" itself counts only once. In fact, only one word of length 9 should be counted (since we are interested in counting subsets and there is only one subset made up of all the letters). Two subsets are taken as different if there is an index of one of the letters that is present in one of the subsets but not in the other.

The first and only line consists of a word $$$s$$$ of length $$$n$$$ ($$$1 \leq n \leq 10^6$$$) are composed of lowercase letters of the alphabet.

Print an integer, the number of subsets of letters of $$$s$$$ that can form the original name written by the pharaoh himself.

taktaktak

10

aaaa

9

abcdef

1