AT_arc060_d [ARC060F] 最良表現

[problemUrl]: https://atcoder.jp/contests/arc060/tasks/arc060_d $ x $ を長さ $ 1 $ 以上の文字列とします。 いかなる文字列 $ y $ および $ 2 $ 以上の整数 $ k $ に対しても、 $ y $ を $ k $ 回繰り返した文字列が $ x $ と異なるならば、 $ x $ を*良い文字列*であると呼ぶことにします。 例えば、`a`, `bbc`, `cdcdc` などは良い文字列ですが、 `aa`, `bbbb`, `cdcdcd` などは良い文字列ではありません。 $ w $ を長さ $ 1 $ 以上の文字列とします。 $ m $ 項からなる列 $ F=(\,f_1,\,f_2,\,...,\,f_m) $ について、 次の条件がともに満たされるならば、$ F $ を $ w $ の*良い表現*と呼ぶことにします。 - すべての $ i\ \,\ (1\ \leq\ i\ \leq\ m) $ について、$ f_i $ は良い文字列である。 - $ f_1,\,f_2,\,...,\,f_m $ をこの順に連結すると $ w $ になる。 例えば、$ w= $`aabb` の場合、$ w $ の良い表現は次の $ 5 $ つとなります。 - $ ( $`aabb`$ ) $ - $ ( $`a`$ , $`abb`$ ) $ - $ ( $`aab`$ , $`b`$ ) $ - $ ( $`a`$ , $`ab`$ , $`b`$ ) $ - $ ( $`a`$ , $`a`$ , $`b`$ , $`b`$ ) $ 文字列 $ w $ の良い表現のうち、項数 $ m $ が最小であるものを、 $ w $ の*最良表現*と呼ぶことにします。 例えば、$ w= $`aabb` の最良表現は $ ( $`aabb`$ ) $ の $ 1 $ つのみとなります。 文字列 $ w $ が与えられます。次の $ 2 $ つを求めてください。 - $ w $ の最良表現の項数 - $ w $ の最良表現の総数を $ 1000000007\ \,\ (=10^9+7) $ で割った余り なお、$ w $ に対し、良い表現が存在することは保証されます。

N/A

N/A

### 制約 - $ 1\ \leq\ |w|\ \leq\ 500000\ \,\ (=5\ \times\ 10^5) $ - $ w $ は英小文字 (`a`-`z`) のみからなる文字列である ### 部分点 - $ 1\ \leq\ |w|\ \leq\ 4000 $ を満たすデータセットに正解した場合は、$ 400 $ 点が与えられる。 ### Sample Explanation 2 \- この入力に対しては、項数が $ 2 $ の最良表現が以下の $ 3 $ 通り存在します。 - $ ( $`b`$ , $`cbc`$ ) $ - $ ( $`bc`$ , $`bc`$ ) $ - $ ( $`bcb`$ , $`c`$ ) $