Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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 で割った余りを出力せよ。
入力例 1
aab
出力例 1
1 1
入力例 2
bcbc
出力例 2
2 3
- この入力に対しては、項数が 2 の最良表現が以下の 3 通り存在します。
- (
b
,cbc
) - (
bc
,bc
) - (
bcb
,c
)
- (
入力例 3
ddd
出力例 3
3 1
Score : 900 points
Problem Statement
Let x be a string of length at least 1.
We will call x a good string, if for any string y and any integer k (k \geq 2), the string obtained by concatenating k copies of y is different from x.
For example, a
, bbc
and cdcdc
are good strings, while aa
, bbbb
and cdcdcd
are not.
Let w be a string of length at least 1. For a sequence F=(\,f_1,\,f_2,\,...,\,f_m) consisting of m elements, we will call F a good representation of w, if the following conditions are both satisfied:
- For any i \, (1 \leq i \leq m), f_i is a good string.
- The string obtained by concatenating f_1,\,f_2,\,...,\,f_m in this order, is w.
For example, when w=aabb
, there are five good representations of w:
- (
aabb
) - (
a
,abb
) - (
aab
,b
) - (
a
,ab
,b
) - (
a
,a
,b
,b
)
Among the good representations of w, the ones with the smallest number of elements are called the best representations of w.
For example, there are only one best representation of w=aabb
: (aabb
).
You are given a string w. Find the following:
- the number of elements of a best representation of w
- the number of the best representations of w, modulo 1000000007 \, (=10^9+7)
(It is guaranteed that a good representation of w always exists.)
Constraints
- 1 \leq |w| \leq 500000 \, (=5 \times 10^5)
- w consists of lowercase letters (
a
-z
).
Partial Score
- 400 points will be awarded for passing the test set satisfying 1 \leq |w| \leq 4000.
Input
The input is given from Standard Input in the following format:
w
Output
Print 2 lines.
- In the first line, print the number of elements of a best representation of w.
- In the second line, print the number of the best representations of w, modulo 1000000007.
Sample Input 1
aab
Sample Output 1
1 1
Sample Input 2
bcbc
Sample Output 2
2 3
- In this case, there are 3 best representations of 2 elements:
- (
b
,cbc
) - (
bc
,bc
) - (
bcb
,c
)
- (
Sample Input 3
ddd
Sample Output 3
3 1