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