分数: 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