Transformation of Polynomial Coefficients

After studying the binomial theorem, the math teacher gave the class a problem. Given an integer degree n, a constant t, and a sequence of coefficients a_k for 0 \le k \le n defined by the recurrence

$$\begin{cases} a_0=1, \\ a_k = (1234\cdot a_{k-1} + 5678) \bmod 3389, \quad k>0, \end{cases} $$

we know that the polynomial

$$\sum_{k=0}^n a_kx^k$$

can be uniquely represented as

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

Your task is to compute the value of a specified coefficient b_m (with 0 \le m \le n). By expanding x=(x-t)+t and applying the binomial expansion, it can be shown that

$$b_m = \sum_{j=m}^{n} a_j \cdot \binom{j}{m} t^{j-m}. $$

Note that the sequence \(a_k\) is generated using the recurrence modulo 3389, but the coefficient \(b_m\) is to be computed exactly (i.e. as an integer without taking any modulus).

inputFormat

The input consists of a single line containing three space-separated integers:

• n (degree of the polynomial, where n \ge 0),
• t (the constant in the expression), and
• m (the index of the coefficient b_m to compute, with 0 \le m \le n).

outputFormat

Output a single integer representing the value of b_m computed as

$$b_m = \sum_{j=m}^{n} a_j \cdot \binom{j}{m} t^{j-m}, $$

where the sequence \(a_k\) is defined by

$$\begin{cases} a_0 = 1,\\ a_k = (1234 \cdot a_{k-1} + 5678) \bmod 3389, \quad k > 0. \end{cases} $$

sample

3 2 1

37474