No.599 回文かい
タグ : / 解いたユーザー数 112
作問者 :
koyumeishi
/ テスター :
conf
問題文
"水道水" は回文それ 回文かい！
文字列 $S$ を $k (\geq 1)$ 個の空でない部分文字列に分解し、 先頭から順に $ T_1, T_2, \dots , T_k $ とします。
($ S = T_1 + T_2 + \dots + T_k $ , $ |T_i| \geq 1 $)
全ての $i (1 \leq i \leq k)$ について $T_i = T_{k-i+1}$ が成り立つとき、
列$T( = [T_1,T_2,\dots,T_k] )$ は文字列 $S$ の 回文かい分解 であるといいます。
文字列 $S$ が与えられるので、 何通りの 回文かい分解 が考えられるか計算してください。
答えが非常に大きくなる場合があるので、 $1,000,000,007$ で割った余りを出力してください。
入力
$S$
$S$ は次の制約を満たします。
$1 \leq |S| \leq 10^4$
$S$ は 小文字のアルファベット 'a' - 'z' のみで構成される
出力
何通りの 回文かい分解 が考えられるか、$1,000,000,007$ で割った余りを出力してください。
サンプル
サンプル1
入力
abc
出力
1
T = ["abc"] が 回文かい分解 になります。
サンプル2
入力
suidousui
出力
2
T = ["suidousui"]
T = ["sui", "dou", "sui"]
サンプル3
入力
kaibunkaibunkai
出力
3
T = ["kaibunkaibunkai"]
T = ["kai", "bunkaibun", "kai"]
T = ["kai", "bun", "kai", "bun", "kai"]
サンプル4
入力
aaaaa
出力
4
T = ["aaaaa"]
T = ["aa", "a", "aa"]
T = ["a", "aaa", "a"]
T = ["a", "a", "a", "a", "a"]
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。