配点 : $900$ 点

問題文

$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$ に対し、良い表現が存在することは保証されます。

制約

• $1 \leq |w| \leq 500000 \, (=5 \times 10^5)$
• $w$ は英小文字 (a-z) のみからなる文字列である

部分点

• $1 \leq |w| \leq 4000$ を満たすデータセットに正解した場合は、$400$ 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

$w$

出力

出力は $2$ 行からなる。

• $1$ 行目に、$w$ の最良表現の項数を出力せよ。
• $2$ 行目に、$w$ の最良表現の総数を $1000000007$ で割った余りを出力せよ。

aab

1
1

bcbc

2
3

• この入力に対しては、項数が $2$ の最良表現が以下の $3$ 通り存在します。- $($b$,$cbc$)$
  • $($bc$,$bc$)$
  • $($bcb$,$c$)$
• $($b$,$cbc$)$
• $($bc$,$bc$)$
• $($bcb$,$c$)$

ddd

3
1