#XMOJ12270. PPAP

PPAP

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:ppap.in 输出文件:ppap.out

设 $P_1,P_2,P_3$ 是长度至少为 $1$ 的任意回文字符串,$A$ 是长度至少为 $1$ 的任意字符串。

给定字符串 $S$。

将 $P_1,P_2,A,P_3$ 按顺序拼接得到字符串 $PPAP$。求满足 $PPAP = S$ 的四元组 $(P_1,P_2,A,P_3)$ 一共有多少种。

输入格式

第一行一个字符串 $S$。

输出格式

输出答案对应的整数。

样例

样例 1

testsetlevelisminim

8

样例说明:

一共有下面8组:

- (t, e, stsetlevelis, minim)

- (t, e, stsetlevelismini, m)

- (t, estse, tlevelis, minim)

- (t, estse, tlevelismini, m)

- (testset, l, evelis, minim)

- (testset, l, evelismini, m)

- (testset, level, is, minim)

- (testset, level, ismini, m)

样例 2

xxoxxxxoxxoxxoxxxxoxxxxoxxxxoxxoxxoxxxxoxx

92

样例 3

ppppppppppppppppapppppppp

1009

数据范围

对于 10% 的数据,$|S| \le 10$。

对于 20% 的数据,$|S| \le 10^5$。

对于 100% 的数据,$4 \le |S| \le 500000$,$S$ 仅由半角小写英文字母构成。