Description

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.

Input Format

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 Format

Output one line containing the value of $b_m$.

3
2
2

10536

Hint

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