如果存在整数 $m \ge 1$ 和字符串 $w_0, w_1, \dots, w_m$，使得满足以下条件，则称字符串 $t$ 为字符串 $w$ 的“平滑变换”（smooth transformation）：

• $w_0 = w$，且当 $0 < i \le m$ 时 $|w_i| = |w|$；
• 当 $0 < i \le m$ 时，$w_i$ 与 $w_{i-1}$ 至多在一个位置上不同；
• $t = w_0 w_1 \dots w_m$。

给定一个字符串 $s = s_1 s_2 \dots s_{|s|}$。求满足 $1 \le i < j < k \le |s|$ 且 $s_{i \dots k} = s_i s_{i+1} \dots s_k$ 是 $s_{i \dots j} = s_i s_{i+1} \dots s_j$ 的平滑变换的下标三元组 $(i, j, k)$ 的数量。

输入格式

输入仅一行，包含字符串 $s$ ($4 \le |s| \le 10^5$)，由小写英文字母组成。

输出格式

输出所求的三元组数量。

样例

输入格式 1

abcababc

输出格式 1

5

说明

在样例测试用例中，三元组为 $(1, 3, 6), (3, 4, 6), (3, 4, 8), (4, 5, 7)$ 和 $(5, 6, 8)$。