10447: #2098. 「CQOI2015」多项式

在学习完二项式定理后，数学老师给出了一道题目：已知整数 $n$、$t$ 和 ak a_k a​k​​（$0\le k\le n$），求 bk b_k b​k​​（$0\le k\le n$）的表达式使得

∑k=0nakxk=∑k=0nbk(x−t)k \sum\limits_{k = 0} ^ n a_k x ^ k = \sum\limits_{k = 0} ^ n b_k (x - t) ^ k ​k=0​∑​n​​a​k​​x​k​​=​k=0​∑​n​​b​k​​(x−t)​k​​

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

$$a_k=\{\begin{array}{cc}(1234\cdot a_{k-1}+5678)mod3389& k>0\\ 1& k=0\end{array}$$

输入格式

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

输出格式

输出一行，为 bm b_m b​m​​ 的值。

样例

样例输入

3
2
2

样例输出

10536

数据范围与提示

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