题目描述

Farmer John 有一个秘密消息要防止他的奶牛们知道，消息是一个长度至少为 $2$ 的由字符 $A \dots Z$ 组成的字符串。

为了加密他的消息， FJ 对它进行了一系列的“操作”，对于应用到字符串 $S$ 的操作，首先删掉 $S$ 的第一个或者最后一个字符来将它缩短，然后将原先的 $S$ 接到这个字符串的前面或者后面。例如，一次对于字符串 ABCD 的操作可能得到四种字符串：

BCDABCD
ABCABCD
ABCDABC
ABCDBCD

给定被加密后的字符串，请计算出 FJ 有多少种可能的方法，对一个初始串应用一系列操作后，可以得到这个目标串。即便得到了相同的加密串，不同的操作序列就算作不同的方法。例如，有四种不同的方法对 AA 进行操作后得到 AAA ，对应于上述四种可能的操作。

输入格式

第 $1$ 行：一个长最多为 $100$ 的字符串。

输出格式

第 $1$ 行：FJ 对一个长度至少为 $2$ 的初始串进行一次或者多次连续操作后，能够得到目标串的方法数量。如果没有方法，输出 0 。

ABABA

6

提示

这里是 FJ 可以得到 ABABA 的不同方法：

1. 开始于 ABA -> AB + ABA
2. 开始于 ABA -> ABA + BA
3. 开始于 AB -> AB + A -> AB + ABA
4. 开始于 AB -> AB + A -> ABA + BA
5. 开始于 BA -> A + BA -> AB + ABA
6. 开始于 BA -> A + BA -> ABA + BA