#abc304f. [abc304_f]Shift Table

[abc304_f]Shift Table

给出长度为 2n1052\le n\le 10^5 仅由 #. 的字符串 ss,对于任意的 mn(0<m<n)m|n(0<m<n),你可以决定字符串 tt 的前 mm 个位置是 # 还是 .,对于第 i>mi>m 个位置,字符与第 imi-m 个位置相同。要求对于位置 1in1\le i\le n 字符串 sstt 必须有一个是 #。注意不同的 mm 可能有相同的方案。问 tt 的方案数对 998244353998244353 取模的结果。