Farmer John の秘密のメッセージは、長さが少なくとも 2 で A..Z の文字だけを含む文字列で、牛には隠したいものです。

暗号化には一連の操作を使います。文字列 $S$ への操作では、先頭の一部（全部は不可）または末尾の一部（全部は不可）を取り除いて $S$ を短くし、元の $S$ をその先頭または末尾に付けます。例えば ABC に 1 回操作すると次の 8 通りになります。

AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC

最終的な暗号文字列から、ある元の文字列に 1 回以上の操作を行って生成する方法数を求めてください。同じ暗号結果でも操作は別として数えます。例えば AA から AAA を作るのは 4 通りです。

答えを 2014 で割った余りを出力してください。

入力

• 1 行目：長さが高々 100 の暗号文字列。

出力

• 1 行目：長さが少なくとも 2 の元の文字列に 1 回以上の連続する操作でこの文字列を生成する方法数を 2014 で割った余り。方法がなければ 0。

入出力例

入力 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