String Splitting with Odd Frequency Constraint

Given a string (S) consisting of lowercase letters, count the number of ways to split (S) into three parts of the form [ S = (AB)^i C,\ i \ge 1,
] where the string (S[0:j]) (with (2 \le j \le |S|-1)) can be partitioned into (i) copies of the concatenation of two non-empty strings (A) and (B) (i.e. (X = AB) with (|X| \ge 2)), and (C = S[j:,|S|]) is non-empty. In each valid splitting, the choice of (A) and (B) is made by splitting the block (X = S[0:d]) (where (d = |A|+|B|) is a divisor of (j); note that when (j = d) the pattern repeats only once, which is always valid) at some position (1 \le k < d) so that (A = S[0:k]) and (B = S[k:d]). Furthermore, let (F(T)) denote the number of distinct characters in string (T) that appear an odd number of times. A splitting is considered valid if and only if (F(A) \le F(C)).

Two splittings are considered different if at least one of the strings (A), (B) or (C) is different.

Your task is to compute the total number of valid splitting schemes for (S).

inputFormat

A single line containing the string (S) ((1 \le |S| \le 10^3)).

outputFormat

Output a single integer representing the total number of valid splitting schemes.

sample

ababab

8