← 返回题目列表

AtCoder · pakencamp_2024_day3_1_j

J. 相邻最大

中文机器翻译题面 查看原题

配点 : 100 点

問題文

正整数 N 。满足以下条件的长度 N 的正整数序列 A=(A_1,A_2,\dots,A_N) 的数量 除以 998244353 求余数。

  • 在顶部 编号为 1,2,\dots,N 并得到了一个号码 N 顶点简单无向连通图 存在满足以下条件的 G 。
    • 任何整数 i (1 \leq i \leq N) ,G 中的顶点 与 i 相邻的顶点的最大顶点数为 如果正确答案是满足 A_i 。

制約

  • 2 \leq N \leq 200000
  • 所有输入均为整数 左起第

部分点

  • N \leq 200 的数据集,30 给予积分。
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 70 给予积分。

入力

输入是按以下格式从标准输入给出的。

N

出力

输出答案。


入力例 1

3

出力例 1

3

A 可能的整数序列是(2,3,2),(3,1,1),(3,3,2) 的 3 一。


入力例 2

5

出力例 2

99

入力例 3

10

出力例 3

14352615