#2049. 「CQOI2015」多项式

「CQOI2015」多项式

说明

在学习完二项式定理后,数学老师给出了一道题目:已知整数 n n t t ak a_k 0kn 0 \leq k \leq n ),求 bk b_k 0kn 0 \leq k \leq n )的表达式使得

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

同学们很快算出了答案。见大家这么快就搞定了,老师便布置了一个更 BT 的作业:计算某个 bm b_m 的具体数值!接着便在黑板上写下了 n n t t 的数值,由于 ak a_k 实在太多,不能全写在黑板上,老师只给出了一个 ak a_k 的递推式,让学生自行计算 ak a_k

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

输入格式

输入文件共三行,第一行为一个正整数 n n ,第二行为一个非负整数 tt ,第三行为一个非负整数 m m

输出格式

输出一行,为 bm b_m 的值。

样例

3
2
2
10536

数据范围与提示

对于 100% 100\% 的数据,$ 0 < n \leq 10 ^ {3000}, 0 \leq t \leq 10000, 0 \leq n - m \leq 5 $。