問題文

$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$ で割った余りを出力せよ。

入力例 1

aab

出力例 1

1
1

入力例 2

bcbc

出力例 2

2
3

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

入力例 3

ddd

出力例 3

3
1