Shift Table

AtCoder

IDabc304_f

Time2000ms

Memory256MB

Difficulty—

Takahashi and Aoki will work part-time for the next $N$ days. Takahashi's shift schedule is given by the string $S$, where the $i$\-th character of $S$ is `#` if he works on the $i$\-th day, and `.` if he is absent on the $i$\-th day. Based on this, Aoki created his shift schedule as follows. * First, take a positive divisor $M$ of $N$ that is not equal to $N$. * Next, decide the attendance for the first $M$ days. * Finally, for $i = 1, 2, \ldots, N - M$ in this order, decide the attendance for the $(M + i)$\-th day so that it matches the attendance for the $i$\-th day. Note that different values of $M$ may lead to the same final shift schedule. Find the number of possible shift schedules for Aoki such that at least one of Takahashi and Aoki works on each of the $N$ days, modulo $998244353$. ## Constraints * $N$ is an integer between $2$ and $10^5$, inclusive. * $S$ is a string of length $N$ consisting of `#` and `.`. ## Input The input is given from Standard Input in the following format: $N$ $S$ [samples]

Samples

Input #1

6
##.#.#

Output #1

3

Takahashi works on days $1$, $2$, $4$, and $6$.  
Let $T$ be the string representing Aoki's shift schedule, where the $i$\-th character of $T$ is `#` if he works on the $i$\-th day, and `.` if he is absent on the $i$\-th day.  
There are three possible strings for $T$: `######`, `#.#.#.`, and `.##.##`.
The first shift schedule can be realized by choosing $M = 1$ or $2$ or $3$, the second by choosing $M = 2$, and the third by choosing $M = 3$.

Input #2

7
...####

Output #2

Input #3

12
####.####.##

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Shift Table",
    "description": {
      "content": "Takahashi and Aoki will work part-time for the next $N$ days.   Takahashi's shift schedule is given by the string $S$, where the $i$\\-th character of $S$ is `#` if he works on the $i$\\-th day, and `.`",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc304_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi and Aoki will work part-time for the next $N$ days.  \nTakahashi's shift schedule is given by the string $S$, where the $i$\\-th character of $S$ is `#` if he works on the $i$\\-th day, and `.`...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments