Duplicate

AtCoder

IDabc313_e

Time2000ms

Memory256MB

Difficulty—

For a string $S$ consisting of digits from `1` through `9`, let $f(S)$ be the string $T$ obtained by the following procedure. ($S_i$ denotes the $i$\-th character of $S$.) * Let $T$ be an initially empty string. * For $i=1, 2, \dots, |S| - 1$, perform the following operation: * Append $n$ copies of $S_i$ to the tail of $T$, where $n$ is the value when $S_{i+1}$ is interpreted as an integer. For example, $S =$ `313` yields $f(S) =$ `3111` by the following steps. * $T$ is initially empty. * For $i=1$, we have $n = 1$. Append one copy of `3` to $T$, which becomes `3`. * For $i=2$, we have $n = 3$. Append three copies of `1` to $T$, which becomes `3111`. * Terminate the procedure. We obtain $T =$ `3111`. You are given a length-$N$ string $S$ consisting of digits from `1` through `9`. You repeat the following operation until the length of $S$ becomes $1$: replace $S$ with $f(S)$. Find how many times, modulo $998244353$, you perform the operation until you complete it. If you will repeat the operation indefinitely, print `-1` instead. ## Constraints * $2 \leq N \leq 10^6$ * $S$ is a length-$N$ string consisting of `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, and `9`. ## Input The input is given from Standard Input in the following format: $N$ $S$ [samples]

Samples

Input #1

3
313

Output #1

4

If $S =$ `313`, the length of $S$ be comes $1$ after four operations.

*   We have $f(S) =$ `3111`. Replace $S$ with `3111`.
*   We have $f(S) =$ `311`. Replace $S$ with `311`.
*   We have $f(S) =$ `31`. Replace $S$ with `31`.
*   We have $f(S) =$ `3`. Replace $S$ with `3`.
*   Now that the length of $S$ is $1$, terminate the repetition.

Input #2

9
123456789

Output #2

\-1

If $S =$ `123456789`, you indefinitely repeat the operation. In this case, `-1` should be printed.

Input #3

2
11

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Duplicate",
    "description": {
      "content": "For a string $S$ consisting of digits from `1` through `9`, let $f(S)$ be the string $T$ obtained by the following procedure. ($S_i$ denotes the $i$\\-th character of $S$.) *   Let $T$ be an initially",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc313_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a string $S$ consisting of digits from `1` through `9`, let $f(S)$ be the string $T$ obtained by the following procedure. ($S_i$ denotes the $i$\\-th character of $S$.)\n\n*   Let $T$ be an initially...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments