P3169 [CQOI2015] Polynomial

After learning the binomial theorem, the math teacher gave a problem: given integers $n, t$ and $a_k$ ($0\le k\le n$), find the expressions for $b_k$ ($0\le k\le n$) such that: $$ \sum_{k=0}^n a_kx^k=\sum_{k=0}^nb_k(x-t)^k $$ The students quickly worked out the answer. Seeing everyone finish so fast, the teacher assigned an even more brutal task: compute the specific value of some $b_k$. Then the teacher wrote the values of $n, t$ on the blackboard. Since there were too many $a_k$ to write out, the teacher only provided a recurrence for $a_k$ and asked the students to compute it themselves: $$ a_k= \begin{cases} (1234\cdot a_{k-1}+5678)\bmod 3389 & k\gt 0 \\ 1 & k=0 \\ \end{cases} $$ As someone learning competitive programming, you feel this homework is not suitable for manual calculation, so you start coding.

The input consists of three lines. The first line contains a positive integer $n$. The second line contains a non-negative integer $t$. The third line contains a non-negative integer $m$.

Output one line containing the value of $b_m$.

Constraints: - For 20% of the testdata, $t=0$. - For another 30% of the testdata, $n\le 10^5$. - For 100% of the testdata, $0\lt n\le 10^{3000}$, $0\le t\le 10^4$, $0\le n-m\le 5$. Translated by ChatGPT 5