多项式 ### 题目描述 在学习完二项式定理后，数学老师给出了一道题目：已知整数 $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 > 0) \\ 1 (k=0) \\ \end{cases} $$ 正在学习信息竞赛的你觉得这个作业实在不适合手工完成，便敲起了代码…… ### 输入描述 输入文件共三行，第一行为一个正整数 $n$，第二行为一个非负整数 $t$，第三行为一个非负整数 $m$。 其中，$0\lt n\le 10^{3000}$，$0\le t\le 10^4$，$0\le n-m\le 5$。 ### 输出描述 输出一行，为 $b_m$ 的值。 ### 输入输出样例 #### 示例 1 >输入 ``` txt 3 2 2 ``` >输出 ``` txt 10536 ```