Best Representation

AtCoder

IDarc060_d

Time2000ms

Memory256MB

Difficulty—

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`). ## Input The input is given from Standard Input in the following format: $w$ ## Partial Score * $400$ points will be awarded for passing the test set satisfying $1 \leq |w| \leq 4000$. [samples]

Samples

Input #1

aab

Output #1

1
1

Input #2

bcbc

Output #2

2
3

*   In this case, there are $3$ best representations of $2$ elements:
    *   $($`b`$,$`cbc`$)$
    *   $($`bc`$,$`bc`$)$
    *   $($`bcb`$,$`c`$)$

Input #3

ddd

Output #3

3
1

API Response (JSON)

{
  "problem": {
    "name": "Best Representation",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc060_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments