After learning the binomial theorem, the math teacher gave the class a problem: given integers $n$ and $a_k (0 \le k \le n)$, find the expression for $b_k (0 \le k \le n)$ such that:

$$\sum_{k=0}^{n} a_k x^k = \sum_{k=0}^{n} b_k (x - t)^k$$

The students quickly calculated the answer. Seeing that everyone finished so fast, the teacher assigned an even more difficult task: calculate the specific value of a certain $b_m$! The teacher then wrote the values of $n$ and $t$ on the blackboard. Since there were too many $a_k$ values to write them all on the board, the teacher only provided a recurrence relation for $a_k$, asking the students to calculate it themselves:

$$a_k = \begin{cases} (1234 \cdot a_{k-1} + 5678) \pmod{3389} & k > 0 \\ 1 & k = 0 \end{cases}$$

As someone studying for informatics competitions, you feel that this assignment is not suitable for manual completion, so you start writing code...

Input

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

Output

Output a single line containing the value of $b_m$.

Examples

Input 1

3
2
2

Output 1

10536

Note

$a_0 = 1, a_1 = 134, a_2 = 1584, a_3 = 1492$ $b_0 = 18541, b_1 = 24374, b_2 = 10536, b_3 = 1492$ $1492y^3 + 1584y^2 + 134y + 1 = 1492(y - 2)^3 + 10536(y - 2)^2 + 24374(y - 2) + 18541$

Constraints

• For 20% of the data, $t=0$.
• For another 30% of the data, $n \le 100000$.
• For 100% of the data, $0 < n \le 10^{3000}$, $0 \le t \le 10000$, $0 \le n-m \le 5$.