题目描述

农民约翰收到一条的消息，记该消息为长度至少为${2，}$只由大写字母组成的字符串${S，}$他通过一系列操作对${S}$进 行加密。

他的操作为，删除${S}$的前面或者后面的若干个字符（但不删光整个${S}$），并将剩下的部分连接到原字符串${S}$的前 面或者后面。

如对于${S=}$‘${ABC}$’，共有${8}$总可能的操作结果：

${AABC}$

${ABABC}$

${BCABC}$

${CABC}$

${ABCA}$

${ABCAB}$

${ABCBC}$

${ABCC}$

给出加密后的目标字符串，请计算共有多少种加密的方案。

对于同字符的字符串，加密方案不止一种，比如把${AA}$加密成${AAA，}$共有${4}$种加密方案。将你的答案${mod 2014}$后输出。

输入格式

第${1}$行:单个加密字符串的长度不超过${100}$。

输出格式

第${1}$行:

${FJ}$对某个长度至少为${2}$的初始字符串应用一个或多个连续操作来生成这个字符串的方法的数量，用${2014}$模表示。

如果没有这样的方法，则输出为零。

样例

输入样例

ABABA

输出样例

8

提示

以下是${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}$开始

从${ABAB -> ABAB+A}$开始

从${BABA -> A+BABA}$开始