1288: #2098. 「CQOI2015」多项式

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

∑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=0nakxk=k=0nbk(xt)k

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

ak={(1234ak1+5678)mod3389k>01k=0

输入格式

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

输出格式

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

样例

样例输入

3
2
2

样例输出

10536

数据范围与提示

对于 100% 100\% 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<n103000,0t10000,0nm5