Farmer John 有一條不想讓乳牛看到的秘密訊息。這是一個長度至少為 2、僅包含字元 A..Z 的字串。
FJ 透過一系列「操作」加密訊息。對字串 $S$ 的一次操作，先刪除其第一個或最後一個字元以縮短 $S$，然後將原始字串 $S$ 連接到開頭或結尾。例如，對 ABCD 進行一次操作可以得到以下四個字串：
BCDABCD ABCABCD ABCDABC ABCDBCD
給定最終加密字串，請統計 FJ 從某個原始字串開始，執行一次或多次連續操作得到它的方式數。即使得到相同的加密結果，不同操作也算不同方式。例如，從 AA 得到 AAA 有四種不同方式，對應上面的四種操作。
輸入格式
- 第 $1$ 行：長度至多為 100 的字串。
輸出格式
- 第 $1$ 行：從某個長度至少為 2 的原始字串開始，連續執行一次或多次操作得到給定字串的不同方式數。若沒有這樣的方式，輸出零。
範例
輸入格式 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