F - Shift Table Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 525 点

問題文

高橋君と青木君は、これから N 日間アルバイトをします。
高橋君のシフト表は文字列 S により与えられ、S の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤します。
これをもとに、青木君は以下のようにシフト表を作りました。

  • まず、N でない N の正の約数 M をとる。
  • 次に、1 日目から M 日目までの勤怠を決める。
  • 最後に、i = 1, 2, \ldots, N - M の順に M + i 日目の勤怠が i 日目の勤怠と一致するように M + i 日目の勤怠を決める。

ここで、M の値が異なる場合でも最終的にできたシフトが同じものとなることがあることに注意してください。

N 日すべてについて高橋君と青木君の少なくとも一方が出勤することになったとき、青木君のシフト表として考えられるものの個数を 998244353 で割った余りを求めてください。

制約

  • N は 2 以上 10^5 以下の整数
  • S は 長さ N の #、. からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

6
##.#.#

出力例 1

3

高橋君は 1 \cdot 2 \cdot 4 \cdot 6 日目に出勤します。
青木君のシフト表を表す文字列を T とし、青木君は T の i 文字目が # のとき i 日目に出勤、. のとき i 日目に欠勤するとします。
T としてあり得るものは ###### \cdot #.#.#. \cdot .##.## の 3 つです。

1 つめのシフト表は M を 1 または 2 または 3、2 つめのシフト表は M = 2、3 つめのシフト表は M = 3 とすることにより実現できます。

入力例 2

7
...####

出力例 2

1

入力例 3

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

出力例 3

19

Score : 525 points

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