Problem Description

Takahashi has a string $ S $ consisting of lowercase English letters.

Takahashi is curious about how many ways $ S $ can be split into a NIKKEI form. Find the number of ways to split $ S $ into 6 non-empty consecutive substrings that satisfy the following conditions:

• When the split strings are labeled from left to right as $ S_1, S_2, S_3, S_4, S_5, S_6 $, $ S_2 $ and $ S_6 $ are equal, and $ S_3 $ and $ S_4 $ are equal.

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the number of ways to split $ S $ into a NIKKEI form.

Sample Input and Output

Sample Input #1

nikkei

Sample Output #1

1

Sample Input #2

aabbccccddbb

Sample Output #2

4

Sample Input #3

aaaaaaaaaaaaaaa

Sample Output #3

70

Notes/Hints

Constraints

• $6 \leq |S| \leq 500$
• $ S $ consists of lowercase English letters

Sample Explanation 1

The only split that satisfies the conditions is $ S_1 = $ n, $ S_2 = S_6 = $ i, $ S_3 = S_4 = $ k, $ S_5 = $ e.

Sample Explanation 2

The ways to split into a NIKKEI form are:
- $ S_1 = $ aa, $ S_2 = $ bb, $ S_3 = $ cc, $ S_4 = $ cc, $ S_5 = $ dd, $ S_6 = $ bb
- $ S_1 = $ aab, $ S_2 = $ b, $ S_3 = $ cc, $ S_4 = $ cc, $ S_5 = $ ddb, $ S_6 = $ b
- $ S_1 = $ aa, $ S_2 = $ bb, $ S_3 = $ c, $ S_4 = $ c, $ S_5 = $ ccdd, $ S_6 = $ bb
- $ S_1 = $ aab, $ S_2 = $ b, $ S_3 = $ c, $ S_4 = $ c, $ S_5 = $ ccddb, $ S_6 = $ b

There are 4 such ways.

见题面 Input 部分

见题面 Output 部分