题目描述

设 $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$)$ 这一种。

给定字符串 $w$，请你求出以下两项：

• $w$ 的最优表示的项数；
• $w$ 的最优表示的总数对 $1000000007\ (=10^9+7)$ 取模的结果。

保证对于给定的 $w$，一定存在好表示。

输入格式

输入为一行，包含字符串 $w$。

输出格式

输出共两行：

• 第 $1$ 行输出 $w$ 的最优表示的项数。
• 第 $2$ 行输出 $w$ 的最优表示的总数对 $1000000007$ 取模的结果。

样例 1

输入

aab

输出

1
1

样例 2

输入

bcbc

输出

2
3

样例 3

输入

ddd

输出

3
1

说明/提示

限制

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

部分分

• 若能正确解决 $1\leq |w|\leq 4000$ 的数据，将获得 $400$ 分。

样例解释 2

对于该输入，项数为 $2$ 的最优表示共有如下 $3$ 种：

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

由 ChatGPT 4.1 翻译