P5808 [Template] Non-homogeneous Linear Recurrence with Constant Coefficients

As soon as NaCly_Fish arrived in the computer lab, everyone who was solving problems looked at her and laughed. Some shouted, “Fishy, why did you get zero points again!” She did not answer, and said to the coach: “Two math problems, and one data structure problem.” Then she turned on the computer. They deliberately shouted louder, “How can you even write exgcd wrong!”...... NaCly_Fish knew she could not chat with the geniuses in the same lab, so she had to talk to the first-year middle school students next door. Once she asked me, “Have you learned OI?” I nodded slightly. She said, “If you have learned OI, ...... then I will test you. For a homogeneous linear recurrence with constant coefficients, how do you compute it?” I thought, someone who is AFO and last in the lab, how dare she test me? So I turned my head away and ignored her. NaCly_Fish waited for a long time and said sincerely, “You can’t do it, right? ... I will teach you, remember this! You should memorize this algorithm well. You will need it when solving problems in future contests.” I lazily replied, “Who needs you to teach me? Isn’t it just writing the recurrence coefficients in the first column of a matrix, putting the remaining $1$’s along the diagonal, and then doing fast exponentiation?” NaCly_Fish looked very happy, tapped the desk with her two long fingernails, nodded, and said, “Yes, yes! ...... There are four more methods as well, do you know them?”...... **** After NaCly_Fish saw this problem, she could not solve it at all. Since she is so bad at it, please solve this problem and help her.

Given the recurrence: $$a_n = P(n) + \sum\limits_{i=1}^k f_i \times a_{n-i}$$ where $P(x)$ is a polynomial of degree $m$. Given $f_1,f_2,\dots,f_k$, $a_0,a_1,\dots,a_{k-1}$, and the coefficients of $P(x)$, find $a_n$. Output the answer modulo $998244353$.

The first line contains three positive integers $n,m,k$. The second line contains $k$ integers, representing $a_0,a_1,\dots,a_{k-1}$. The third line contains $k$ integers, representing $f_1,f_2,\dots,f_k$. The fourth line contains $m+1$ integers, from low degree to high degree, representing the coefficients of $P(x)$.

Output one line with one integer, representing the answer.

Constraints For $100\%$ of the testdata, $1\le n \le 10^9$, $1\le m,k \le 30000$. Except for the first line, all input numbers are in the range $[0,998244353)$. The testdata has multiple difficulty levels. Translated by ChatGPT 5