#P17730. [2026年福建省队集训]once again

[2026年福建省队集训]once again

题目背景

小青蛙在备课。

小青蛙看到一个题,很快想出来一个多项式做法。

小青蛙看题解,题解说有一个平方做法,但是小青蛙没看懂。

小青蛙又想了一会,虵觉得这题肯定能几乎线性。

但是小青蛙懒得继续想,于是虵把这个题丢给了 GPT-5.5 Thinking (xhigh)。过了 4 分钟 44 秒,GPT 大人果然给了一个符合小青蛙想象的做法。

然后小青蛙很快发现其实还能再加十个零。于是虵把加了二十个零的原题出给了你。

题目描述

给定一个正整数 nn 和一个 01 串 ss。

对于一个长为 nn 的 01 串 tt,如果存在 tt 的某个循环移位,使得 ss 是这个循环移位后的串的子串,那么称 tt 是好的。

换句话说,把 tt 看成一个环,如果能在这个环上从某个位置开始连续读出 ss,那么 tt 是好的。

请你求有多少个长为 nn 的 01 串是好的。答案对 998244353998244353 取模。

注意,两个 01 串只要作为普通字符串不同,就认为它们不同。即使它们互为循环移位,也会被分别计数。

输入格式

第一行包含一个正整数 nn。

第二行包含一个 01 串 ss。

输出格式

输出一个整数,表示好的长为 nn 的 01 串数量对 998244353998244353 取模后的结果。

输入输出样例 #1

输入 #1

2
0

输出 #1

3

输入输出样例 #2

输入 #2

4
1010

输出 #2

2

输入输出样例 #3

输入 #3

20
10101010101010

输出 #3

962

说明/提示

样例 #1 中,好的字符串为 00,01,10,共 33 个。

样例 #2 中,好的字符串为 1010,0101,共 22 个。

对于 15%15\% 的数据,1≤∣s∣≤n≤201\le |s|\le n\le 20;

对于 30%30\% 的数据,1≤∣s∣≤n≤401\le |s|\le n\le 40;

对于 50%50\% 的数据,1≤∣s∣≤n≤40001\le |s|\le n\le 4000;

对于 95%95\% 的数据,1≤∣s∣≤n≤1051\le |s|\le n\le 10^5;

对于 100%100\% 的数据,1≤∣s∣≤1051\le |s|\le 10^5,∣s∣≤n≤1018|s|\le n\le 10^{18},ss 仅包含字符 0 和 1。