[CQOI2015] 多项式

题目描述

在学习完二项式定理后,数学老师给出了一道题目:已知整数 $n,t$ 和 $a_k$($0\le k\le n$),求 $b_k$($0\le k\le n$)的表达式使得: $$ \sum_{k=0}^n a_kx^k=\sum_{k=0}^nb_k(x-t)^k $$ 同学们很快算出了答案。见大家这么快就搞定了,老师便布置了一个更 BT 的作业:计算某个 $b_k$ 的具体数值!接着便在黑板上写下了 $n,t$ 的数值,由于 $a_k$ 实在太多,不能全写在黑板上,老师只给出了一个 $a_k$ 的递推式,让学生自行计算: $$ a_k= \begin{cases} (1234\cdot a_{k-1}+5678)\bmod 3389 & k\gt 0 \\ 1 & k=0 \\ \end{cases} $$ 正在学习信息竞赛的你觉得这个作业实在不适合手工完成,便敲起了代码……

输入输出格式

输入格式


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

输出格式


输出一行,为 $b_m$ 的值。

输入输出样例

输入样例 #1

3
2
2

输出样例 #1

10536

说明

数据范围: 对于 $20\%$ 的数据,$t=0$。 对于另外 $30\%$ 的数据,$n\le 10^5$。 对于 $100\%$ 的数据,$0\lt n\le 10^{3000}$,$0\le t\le 10^4$,$0\le n-m\le 5$。