U648099 [FesdrerOI R19, T4] 渡清欢

 > 清欢难渡情深知多少 > > 红豆把梦扰 > > 星辰不问暮暮又朝朝 > > 尘缘怎么熬 > > 清欢怎渡一碗泪做酒 > > 烟雨尽飘摇 > > 纵相思离肠千结 > > 此情亦难了 > > ——周林枫《渡清欢》

小圆定义一棵无标号有根二叉树 $T$ 的权值 $f _ n (T)$ 为 > 起初，$T$ 上的节点全是白色，小圆将对 $T$ 进行若干（可以为零）次以下操作： > > - 任意选择一个节点 $u$，从 $u$ 开始一直走左子结点（如果有），并染黑走过的所有节点。 > > 权值 $f _ n (T)$ 定义为满足以下条件的本质不同的染色方案数： > > - 恰好有 $n$ 个节点被染成黑色。 > > - 不存在两个相邻的白色点。 > > 小圆认为两种染色方案不同，当且仅当存在一个节点 $u$，使得它们在两种方案中染上了不同颜色。 给定整数 $n$，记所有无标号有根二叉树构成的集合为 $\mathcal S$，小圆想要知道 $$\displaystyle \sum _ {T \in \mathcal S} f _ n (T)$$。 但小圆现在还有 114514 道小方给的题没有写，于是忙于写题的她将任务交给了你。 由于小圆知道你很菜，她只期望你能求出答案对 $998244353$ 取模的结果就好了。 好心的小圆还担心你不会区分两棵不同的无标号有根二叉树，于是她在样例解释里配了图来帮助你。

一行包含一个整数 $n$。

一个整数表示答案。

#### 样例 #1 解释 权值非 $0$ 的无标号有根二叉树及其染色方案如下图：  倒数第二幅图不合法的原因是存在两个白点相邻。 倒数第一幅图不合法的原因是染黑一个点而没有走左子结点继续染黑。 #### 数据范围 对于所有数据，$1 \le n \le 10 ^ 7$。 |测试点编号|$n \le$|特殊性质| |:-:|:-:|:-:| |$1 \sim 4$|$4$|A| |$5 \sim 7$|$50$|无| |$8 \sim 9$|$5000$|^| |$10 \sim 12$|$10 ^ 5$|^| |$13 \sim 17$|$2 \times 10 ^ 5$|^| |$18 \sim 25$|$10 ^ 7$|^| 特殊性质 A：$n =$ 测试点编号。