分数: 900 点
问题陈述
让 x 是一个至少长度的字符串 1。
我们会打电话 x a 好 字符串,如果为任何字符串 y 和任何整数 k (k \geq 2),连接得到的字符串 k 副本 y 不同于 x。
例如, a, bbc 和 cdcdc 是很好的字符串,而 aa, bbbb 和 cdcdcd 不是。
让 w 是一个至少长度的字符串 1。 对于一个序列 F=(\,f_1,\,f_2,\,...,\,f_m) 组成 m 元素, 我们会打电话 F a 良好的代表性 of w,如果同时满足以下条件:
- 对于任何 i \, (1 \leq i \leq m), f_i 是一个很好的字符串。
- 连接得到的字符串 f_1,\,f_2,\,...,\,f_m 按此顺序,是 w.
例如,当 w=aabb,有五个很好的表示 w:
- (
aabb) - (
a,abb) - (
aab,b) - (
a,ab,b) - (
a,a,b,b)
良好的代表 w,元素数量最少的称为 最佳表示 of w。
例如,只有一种最佳表示 w=aabb: (aabb).
给你一个字符串 w。找到以下内容:
- 的最佳表示的元素数量 w
- 的最佳表示数 w,模数 1000000007 \, (=10^9+7)
(保证能够很好地表示 w 始终存在。)
约束
- 1 \leq |w| \leq 500000 \, (=5 \times 10^5)
- w 由小写字母 (
a-z).
部分分数
- 400 通过满足以下条件的测试集将获得积分 1 \leq |w| \leq 4000.
输入
输入由标准输入按以下格式给出:
w
输出
打印 2 行。
- 在第一行中,打印最佳表示的元素数量 w.
- 在第二行中,打印最佳表示的数量 w,模数 1000000007.
示例输入 1
aab
示例输出 1
1 1
示例输入 2
bcbc
示例输出 2
2 3
- 在这种情况下,有 3 的最佳表示 2 元素:
- (
b,cbc) - (
bc,bc) - (
bcb,c)
- (
示例输入 3
ddd
示例输出 3
3 1