Farmer John 有一条不想让奶牛看到的秘密消息。这是一个长度至少为 2、仅包含字符 A..Z 的字符串。
FJ 通过一系列“操作”加密消息。对字符串 $S$ 的一次操作，先删除其第一个或最后一个字符以缩短 $S$，然后将原始字符串 $S$ 连接到开头或结尾。例如，对 ABCD 进行一次操作可以得到以下四个字符串：
BCDABCD ABCABCD ABCDABC ABCDBCD
给定最终加密字符串，请统计 FJ 从某个原始字符串开始，执行一次或多次连续操作得到它的方式数。即使得到相同的加密结果，不同操作也算不同方式。例如，从 AA 得到 AAA 有四种不同方式，对应上面的四种操作。
输入格式
- 第 $1$ 行：长度至多为 100 的字符串。
输出格式
- 第 $1$ 行：从某个长度至少为 2 的原始字符串开始，连续执行一次或多次操作得到给定字符串的不同方式数。若没有这样的方式，输出零。
样例
输入格式 1
ABABA
输出格式 1
6
说明
FJ 得到 ABABA 的不同方式如下：
- 从以下字符串开始：
ABA -> AB+ABA - 从以下字符串开始：
ABA -> ABA+BA - 从以下字符串开始：
AB -> AB+A -> AB+ABA - 从以下字符串开始：
AB -> AB+A -> ABA+BA - 从以下字符串开始：
BA -> A+BA -> AB+ABA - 从以下字符串开始：
BA -> A+BA -> ABA+BA
题目作者：Brian Dean 和 Lewin Gan