题目描述

设 $x$ 是一个长度至少为 $1$ 的字符串。如果对于任意字符串 $y$ 和任意整数 $k (k \geq 2)$，由 $k$ 个 $y$ 的拷贝连接而成的字符串与 $x$ 不同，则称 $x$ 是一个 好字符串 。例如，a、bbc 和 cdcdc 是好字符串，而 aa、bbbb 和 cdcdcd 不是。

设 $w$ 是一个长度至少为 $1$ 的字符串。对于一个由 $m$ 个元素组成的序列 $F=(f_1,f_2,\ldots,f_m)$, 如果满足以下两个条件，则称 $F$ 是 $w$ 的 好表示 ：

• 对于任意 $i (1 \leq i \leq m)$，$f_i$ 是一个好字符串。
• 按照顺序连接 $f_1,f_2,\ldots,f_m$ 得到的字符串是 $w$。

例如，当 $w=$aabb 时，有五个 $w$ 的好表示：

• $($aabb$)$
• $($a$,$abb$)$
• $($aab$,$b$)$
• $($a$,$ab$,$b$)$
• $($a$,$a$,$b$,$b$)$

在 $w$ 的好表示中，元素个数最小的表示被称为 $w$ 的 最佳表示 。例如，$w=$aabb 只有一个最佳表示：$($aabb$)$。

给定一个字符串 $w$。请找出以下内容：

• 最佳表示中的元素个数。
• 最佳表示的数量，模 $1000000007$。

（确保 $w$ 总是存在好表示。）

约束条件

• $1 \leq |w| \leq 500000 (=5 \times 10^5)$
• $w$ 由小写字母 (a-z) 组成。

部分分

• 当通过满足 $1 \leq |w| \leq 4000$ 的测试集时，可获得 $400$ 分。

输入

从标准输入读入输入数据，输入格式如下：

$w$

输出

输出 $2$ 行。

• 在第一行中，输出最佳表示中的元素个数。
• 在第二行中，输出最佳表示的数量，模 $1000000007$。

示例输入1

aab

示例输出1

1
1

示例输入2

bcbc

示例输出2

2
3

在这个例子中，$2$ 个元素有 $3$ 个最佳表示：

• $($b$,$cbc$)$
• $($bc$,$bc$)$
• $($bcb$,$c$)$

示例输入3

ddd

示例输出3

3
1