分数: 800 点
问题陈述
给你一个正整数 N 和长度-N 字符串 s_0s_1\ldots s_{N-1} 仅包含 0 和 1.
考虑一个简单的无向图 G 与 (N+1) 顶点编号 0, 1, 2, \ldots, N,以及以下边:
- 对于每个 i = 0, 1, \ldots, N-1,顶点之间有一条无向边 i 和 (i+1)\bmod N.
- 对于每个 i = 0, 1, \ldots, N-1,顶点之间有一条无向边 i 和 N 当且仅当 s_i =
1. - 没有其他边。
此外,创建一个有向图 G' 通过为每个边缘分配一个方向 G。也就是说,对于每个无向边 \lbrace u, v \rbrace in G,将其替换为有向边 (u, v) 来自 u to v 或有向边 (v, u) 来自 v to u.
对于每个 i = 0, 1, \ldots, N,让 d_i 是顶点的入度 i in G'。打印数字,模数 998244353,具有不同的序列 可以获得 (d_0, d_1, \ldots, d_N) 。
约束
- 3 \leq N \leq 10^6
- N 是一个整数。
- 每个 s_i is
0or1.
输入
输入由标准输入按以下格式给出:
N
s_0s_1\ldots s_{N-1}
输出
打印答案。
样本输入 1
3 010
示例输出 1
14
G 有四个无向边: \lbrace 0, 1 \rbrace, \lbrace 0, 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace。 例如,如果我们将方向分配给每条边 获得 0 \to 1, 2 \to 0, 2 \to 1, 1 \to 3,那么 (d_0, d_1, d_2, d_3) = (1, 2, 0, 1) 。
可能的序列 (d_0, d_1, d_2, d_3) 是 (0, 1, 2, 1), (0, 2, 1, 1), (0, 2, 2, 0), (0, 3, 1, 0), (1, 0, 2, 1), (1, 1, 1, 1), (1, 1, 2, 0), (1, 2, 0, 1), (1, 2, 1, 0), (1, 3, 0, 0), (2, 0, 1, 1), (2, 1, 0, 1), (2, 1, 1, 0), (2, 2, 0, 0),总共 14.
示例输入 2
20 00001100111010100101
示例输出 2
261339902