200603: [AtCoder]ARC060 F - Best Representation

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

设$x$是一个长度至少为1的字符串，我们称$x$是好的，当且仅当对于任意字符串$y$和任意整数$k(k≥2)$，由$y$复制$k$次并连接得到的字符串均与$x$不同。 举个例子，`a`，`bbc`和`cdcdc`是好串，然而`aa`，`bbbb`和`cdcdcd`不是。 设$w$是一个长度至少为1的字符串，对于一个由$m$个元素组成的序列 $F=(f_1,f_2,...,f_m)$，我们称$F$为$w$的一个“亮眼表现”当且仅当下面的条件同时被满足： * 对于任意$i(1≤i≤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$的所有亮眼表现中，元素数量最少的那个（些）亮眼表现被称为$w$的“全场最佳”。举个例子，当$w$='`aabb`'时，$w$的全场最佳只有一个：(`aabb`)。 给你一个字符串$w$，请计算： * $w$的一个全场最佳所含的元素数量 * $w$有多少个全场最佳（对1e9+7取模） (数据保证$w$一定存在亮眼表现)

Source/Category

加入题单

算法标签：