题目描述

Grammy 对字符串有一种独特的理解。

她认为，一个字符串是“正字符串”，当且仅当它按照字典序严格大于它的反转字符串。

现在给定一个字符串 $S$，请计算 $S$ 的所有非空连续子串中，有多少个是正字符串。

输入格式

输入仅一行，包含一个只由小写英文字母组成的字符串 $S$。

输出格式

输出一个整数，表示 $S$ 的正字符串子串数量。

样例 1

输入：
jjikkollp

输出：
4

样例 2

输入：
pbpbppb

输出：
7