排班表

题目描述

高桥和青木将在接下来的 $N$ 天打工。

高桥的排班用字符串 $S$ 给出,其中 $S$ 的第 $i$ 个字符为 # 表示他在第 $i$ 天上班,为 . 表示他在第 $i$ 天休息。

基于此,青木按如下方式制定了自己的排班表。

首先,取一个 $N$ 的正因数 $M$,且 $M \neq N$。

接下来,决定前 $M$ 天的出勤情况。

最后,对于 $i = 1, 2, \ldots, N - M$,按这个顺序决定第 $(M + i)$ 天的出勤情况,使其与第 $i$ 天的出勤情况相同。

注意,不同的 $M$ 值可能得到相同的最终排班表。

求在 $N$ 天中每一天至少高桥和青木中有一个人上班时,青木可能的排班表数量,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

N
S

输出格式

输出答案。

样例

6
##.#.#

3

高桥在第 $1$、$2$、$4$、$6$ 天上班。

设 $T$ 为表示青木排班的字符串,其中 $T$ 的第 $i$ 个字符为 # 表示他在第 $i$ 天上班,为 . 表示他在第 $i$ 天休息。

$T$ 可能的字符串有三种:######、#.#.#.、.##.##。

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

7
...####

1

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

19

数据范围

• $N$ 是 $2$ 到 $10^5$ 之间(含端点)的整数。
• $S$ 是由 # 和 . 组成的长为 $N$ 的字符串。