Sum of Beauties of Substrings

Professor Pang has obtained a dictionary of the elvish language, containing many strings representing elvish words. He defines a partition of a string \( s \) as beautiful if it satisfies the following conditions:

• \( s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6 \), where each \( s_i \) \((1 \leq i \leq 6)\) is a non-empty substring. Here, \( a + b \) denotes the concatenation of the strings \( a \) and \( b \).
• \( s_1 = s_2 = s_5 \) and \( s_3 = s_6 \).

For example, the string "114514" can be partitioned as follows:

[ 114514 = \underbrace{1}{s_1} + \underbrace{1}{s_2} + \underbrace{4}{s_3} + \underbrace{5}{s_4} + \underbrace{1}{s_5} + \underbrace{4}{s_6} ]

Since \( s_1 = s_2 = s_5 = "1" \) and \( s_3 = s_6 = "4" \), this partition is considered beautiful.

The beauty of a string \( s \) is defined as the number of its beautiful partitions. Given a string \( t \), your task is to calculate the sum of the beauties of all substrings of \( t \).

inputFormat

The input consists of a single line containing the string \( t \), consisting of digits and/or letters.

\( 1 \leq |t| \leq 50 \) (where \(|t|\) denotes the length of \( t \)).

outputFormat

Output a single integer, the sum of the beauties of all substrings of \( t \).

sample

114514

3