← 返回题目列表

AtCoder · abc304_f

I. 班次表

中文机器翻译题面 查看原题

分数: 525 点

问题陈述

高桥和青木接下来将兼职工作 N 天。
Takahashi 的轮班时间表由字符串给出 S,其中 i- 第一个字符 S is # 如果他从事 i第一天,以及 . 如果他缺席 i第一天。
基于此,青木制定了如下轮班时间表。

  • 首先取正除数 M of N 不等于 N.
  • 接下来,决定第一场的出席情况 M 天。
  • 最后,对于 i = 1, 2, \ldots, N - M 按此顺序,决定参加者的出席情况 (M + i)- 第天,以便与 i第一天。

请注意,不同的值 M 可能会导致相同的最终班次安排。

求 Aoki 可能的轮班安排数量,使得 Takahashi 和 Aoki 至少有一个在每个班次上工作 N 天,模数 998244353.

约束

  • N 是介于 2 和 10^5,包括在内。
  • S 是一个长度为 N 组成 # 和 ..

输入

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

N
S

输出

打印答案。


示例输入 1

6
##.#.#

示例输出 1

3

高桥白天工作 1, 2, 4,和 6.
让 T 是代表青木的轮班时间表的字符串,其中 i- 第一个字符 T is # 如果他从事 i第一天,以及 . 如果他缺席 i第一天。
存在三个可能的字符串 T: ######, #.#.#.,和 .##.##.

第一班排班可以通过选择来实现 M = 1 or 2 or 3,选择第二个 M = 2,然后选择第三个 M = 3.


示例输入 2

7
...####

示例输出 2

1

示例输入 3

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

示例输出 3

19