103045: [Atcoder]ABC304 F - Shift Table

Problem Statement

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$

Output

Print the answer.

Sample Input 1

6
##.#.#

Sample 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$.

Sample Input 2

7
...####

Sample Output 2

1

Sample Input 3

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

Sample Output 3

19

问题描述

Takahashi 和 Aoki 将在未来 $N$ 天做兼职工作。
Takahashi 的排班表是一个字符串 $S$，其中 $S$ 的第 $i$ 个字符为 # 表示他将在第 $i$ 天工作，而 . 表示他将在第 $i$ 天休息。
根据这个，Aoki 创建了他的排班表如下。

• 首先，选择一个正除数 $M$，且 $M$ 不等于 $N$。
• 其次，决定前 $M$ 天的出勤情况。
• 最后，按照顺序为 $i = 1, 2, \ldots, N - M$，决定第 $(M + i)$ 天的出勤情况，使其与第 $i$ 天的出勤情况相匹配。

注意，不同的 $M$ 值可能导致最终排班表相同。

求满足在 $N$ 天中至少有一天 Takahashi 和 Aoki 其中一人工作的排班表的数量，对 $998244353$ 取模。

约束条件

• $N$ 是一个介于 $2$ 和 $10^5$ 之间的整数，包括 $2$ 和 $10^5$。
• $S$ 是一个长度为 $N$ 的字符串，由 # 和 . 组成。

输入

输入数据从标准输入中给出，格式如下：

$N$
$S$

输出

输出答案。

样例输入 1

6
##.#.#

样例输出 1

3

Takahashi 在第 $1$、$2$、$4$ 和 $6$ 天工作。
假设 $T$ 表示 Aoki 的排班表，其中 $T$ 的第 $i$ 个字符为 # 表示他将在第 $i$ 天工作，而 . 表示他将在第 $i$ 天休息。
对于 $T$，有三个可能的字符串：######、#.#.#. 和 .##.##。

第一个排班表可以通过选择 $M = 1$ 或 $2$ 或 $3$ 实现，第二个排班表可以通过选择 $M = 2$ 实现，第三个排班表可以通过选择 $M = 3$ 实现。

样例输入 2

7
...####

样例输出 2

1

样例输入 3

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

样例输出 3

19