[AdditionalFile151.zip](file://AdditionalFile151.zip?type=additional_file)

#151. 多项式求立方根

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB | 显示标签 通过: 118 | 提交: 268

题目描述

这是一道 OJ 测试题。

给定 $n$ 次多项式 $F(x)$，求 $G(x)$ 满足 $G^3(x) \equiv F(x) \pmod{x^{n+1}}$，也即，$G(x) \equiv \sqrt[3]{F(x)} \pmod{x^{n+1}}$，保证常数项非零。

注意 $\sqrt[3]{F(x)}$ 在模 $998244353$ 下唯一。

所有运算在模 $998244353$ 下进行。

输入格式

第一行一个正整数 $n$，意义见上。

第二行 $n + 1$ 个正整数，表示 $F(x)$ 的 $0$ 次项系数至 $n$ 次项系数。

输出格式

共一行，从低次项至高次项输出系数。

样例

输入

7
1 9 2 6 0 8 1 7

输出

1 3 665496227 43 221831826 665497874 419004875 813465047

数据范围与提示

保证 $1 \le n \le 10^5$。