1016-[CQOI2015]多项式_重庆历年省选真题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在学习完二项式定理后，数学老师给出了一道题目：已知整数n,t和ak(0≤k≤n)，求bk(0≤k≤n)的表达式使得:

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

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

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

正在学习信息竞赛的你觉得这个作业实在不适合手工完成，便敲起了代码……

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

输出一行，为N的值。

示例1

复制

3
2
2

复制

对于 20% 的数据，。

对于另外 30% 的数据，

对于 100% 的数据，