← 返回题目列表

AtCoder · abc222_h

H. 美丽的二叉树

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

分数: 600 点

问题陈述

对于正整数 N,满足以下条件的有根二叉树被称为 美丽的度二叉树 N.

  • 每个顶点都有 0 or 1 。
  • 作为叶子的每个顶点都有 1 。
  • 最多可以进行以下操作 N-1 次,使得根有 其上写有 N ,其他顶点有 0 。
    • 选择顶点 u 和 v,其中 v 必须是 u 或“的孩子”的孩子 u。”让 a_u \gets a_u + a_v, a_v \gets 0,其中 a_u 和 a_v 是写在上面的数字 u 和 v。

鉴于 N,求模数 998244353,美丽的度数二叉树 N.

约束

  • 1 \leq N \leq 10^7
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N

输出

打印答案。


示例输入 1

1

示例输出 1

1

满足条件的唯一二叉树是具有一个顶点且其根具有 1 。


示例输入 2

2

示例输出 2

6

满足条件的二叉树是如下所示的六棵树。

image


示例输入 3

222

示例输出 3

987355927

示例输入 4

222222

示例输出 4

675337738