Farmer John には牛たちに隠したい秘密のメッセージがあります。長さが 2 以上で、A..Z の文字だけからなる文字列です。
暗号化のため、FJ は一連の「操作」を行います。文字列 $S$ への操作は、まず先頭または末尾の文字を削除して $S$ を短くし、その後、元の文字列 $S$ を先頭または末尾に連結します。例えば ABCD に一度操作すると、次の四つの文字列が得られます。
BCDABCD ABCABCD ABCDABC ABCDBCD
最終的な暗号化文字列が与えられます。何らかの元の文字列に 1 回以上の連続した操作を行って、FJ がこの文字列を作る方法の数を数えてください。同じ暗号化結果を得る操作も別々に数えます。例えば AA から AAA を作る方法は、上の四つの操作に対応して 4 通りあります。
入力
- $1$ 行目：長さが最大 100 の文字列。
出力
- $1$ 行目：長さが 2 以上の何らかの元の文字列に 1 回以上連続して操作を行い、与えられた文字列を作る異なる方法の数。方法がなければゼロを出力してください。
入出力例
入力 1
ABABA
出力 1
6
注記
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
問題作成：Brian Dean と Lewin Gan