← 返回题目列表

AtCoder · arc060_d

F. 最佳代表

中文机器翻译题面 查看原题

分数: 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