题目描述

点击此处下载 2024 实验室一面题解

范德蒙德卷积是计算多项式乘积的一种有效方式。

范德蒙德矩阵（Van der Monde Matrix）

范德蒙德矩阵是一个在数学和统计学中使用的矩阵，其元素由幂次生成。具体来说，对于一个范德蒙德矩阵 V ，假设有 n个列向量，每个列向量 j （其中 j = 1, 2, ...n ）和行索引 i （其中 i = 0, 1, ...n-1 ）的元素定义为：

这里，x_j 是一个给定的数字序列。范德蒙德矩阵的一个关键特性是，它可以用来解决涉及多项式插值的问题。

范德蒙德卷积（Van der Monde Convolution）

范德蒙德卷积不是范德蒙德矩阵的直接扩展，但它与多项式的卷积相关。在处理多项式时，卷积通常用于计算两个多项式序列的乘积。

定义

给定两个多项式 P(x) 和 Q(x)，其系数分别为 p_0,p_1,...,p_m 和 q_0,q_1,...,q_n 它们的卷积定义为：

使用方法

1. **构建范德蒙德矩阵：**构建一个 (m+n)×(m+n)的范德蒙德矩阵，其中 m 和 n 分别是两个多项式的次数。
2. **计算卷积系数：**使用范德蒙德矩阵，将一个多项式的系数向量与另一个多项式的系数向量的转置相乘，得到卷积系数。

现在给你一个递推公式：

求该数列的第 n 项。由于答案可能过大，你只需要输出答案对 998244353 取模后的值。

输入描述

一个正整数 n (1≤n≤10000000000000000) 。

输出描述

一个整数，对应答案。

示例 1

输入

1

输出

2