As you all know, you are participating in the SYSUCPC (SYSU Counting Periodic-string Contest) finals.
A string is considered if and only if it can be rearranged into a perfectly periodic string with as its period (which means several repetitions). For example, are all , while are not. Given a string , determine how many of its substrings are .
A string is a substring of a string if can be obtained from by the deletion of several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.
输入格式
The only line contains a single string . It is guaranteed that only contains lowercase English letters.
输出格式
An integer, representing the number of substrings of .
