当前没有测试数据。

F - Shift Table

得分：525分

问题描述

Takahashi和Aoki将在接下来的 N 天里做兼职工作。
Takahashi的班次安排由字符串 S 给出，其中 S 的第 i 个字符是 # 表示他在第 i 天工作，. 表示他在第 i 天上班。
基于此，Aoki如下创建了他的班次表。

• 首先，取 N 的正因数 M 且 M 不等于 N。
• 接下来，确定前 M 天的上班情况。
• 最后，按照顺序对于 i=1, 2, ..., N-M，确定第 M+i 天的上班情况，使其与第 i 天的上班情况相同。

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

找出 Aoki 可能的班次表数量，使得 Takahashi 和 Aoki 中至少有一个人在 N 天中的每一天上班，结果对 998244353 取模。

约束条件

• N 是一个大于等于 2 且小于等于 $10^5$ 的整数。
• S 是一个长度为 N 的字符串，由 # 和 . 组成。

输入

从标准输入中以以下格式获取输入：

$N$

$S$

输出

输出结果。

6
##.#.#

3

Takahashi 在第 1、2、4 和 6 天上班。
令 T 表示 Aoki 的班次表，其中 T 的第 i 个字符是 # 表示他在第 i 天工作，. 表示他在第 i 天上班。
存在三个可能的字符串 T：######、#.#.#. 和 .##.##。

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

7
...####

1

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

19