F-卷积_牛客竞赛数学专题班原根与NTT（原根、指标、NTT、分治FFT/NTT、多项式牛顿迭代）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛为了考验你卷积的能力，出了一道简单的卷积题给你做。

定义生成函数： $F(x)=\sum_{i=1} f_ix^i$ ， $f_i=af_{i-1}+bf_{i-2}|(i>=2),f_0=0,f_1=1$

现在要你求 $\sum_{i=1} F^i(x)$ 的第n项 $\mod 998244353$ 的值。

n a b

一个答案一行

示例1

复制

3 1 1

复制

$\\F(x)=x+x^2+2x^3+...<br />\\F^2(x)=x^2+2x^3+...<br />\\F^3(x)=x^3+...<br />\\x^3这一项的系数之和为5，答案即为5<br />\\F^i(x)=(F(x))^i$

示例2

复制

234 32 12

复制

455012190

对于20%的数据：1<=n<=500
对于40%的数据：1<=n<=3000
对于60%的数据：1<=n<=200000
对于另外20%的数据：a<=1,b<=1
对于100%数据：1≤n≤2000000，0<=a,b<998244353