問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は S を NIKKEI 型に分割する方法が何通りあるか気になっています。 S を 6 つの空でない連続する文字列に分割する方法であって、次の条件を満たすものの個数を求めてください。

• S を分割してできた文字列を前から順に S_1, S_2, S_3, S_4, S_5, S_6 としたとき、S_2 と S_6 が等しく、かつ S_3 と S_4 が等しい。

制約

• 6 \leq |S| \leq 500
• S は英小文字から成る

入力例 1

nikkei

出力例 1

1

条件を満たす分割は、S_1 = n , S_2 = S_6 = i , S_3 = S_4 = k , S_5 = e のみです。

入力例 2

aabbccccddbb

出力例 2

4

NIKKEI 型に分割する方法は、

• 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

の 4 通りあります。

入力例 3

aaaaaaaaaaaaaaa

出力例 3

70