Farmer John 有一条想瞒着奶牛的秘密消息：长度至少为 2、仅包含 A..Z 字符的字符串。

为加密消息，FJ 连续应用若干“操作”。对字符串 $S$ 的一次操作先删去开头的一部分（不能全部）字符，或结尾的一部分（不能全部）字符，缩短 $S$，然后把原字符串 $S$ 接在其开头或结尾。例如，对 ABC 操作一次可得到八种字符串：

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

给定最终加密字符串，请统计从某个原字符串出发，应用一次或多次操作生成它的方式数。即使得到相同加密结果，操作仍视为不同。例如，从 AA 得到 AAA 有四种不同方式。

输出答案对 2014 取模的结果。

输入格式

• 第 1 行：一个长度至多为 100 的加密字符串。

输出格式

• 第 1 行：从某个长度至少为 2 的原字符串出发，应用一次或多次连续操作得到该字符串的方式数，对 2014 取模。若没有这样的方式，输出零。

样例

输入格式 1

ABABA

输出格式 1

8

说明

以下是生成 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
7. 从以下字符串开始： ABAB -> ABAB+A
8. 从以下字符串开始： BABA -> A+BABA

题目作者：Brian Dean 和 Lewin Gan