在学习完二项式定理后，数学老师给出了一道题目：已知整数 n n n、t t t 和 ak a_k ak（0≤k≤n 0 \leq k \leq n 0≤k≤n），求 bk b_k bk（0≤k≤n 0 \leq k \leq n 0≤k≤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∑nakxk=k=0∑nbk(x−t)k
同学们很快算出了答案。见大家这么快就搞定了，老师便布置了一个更 BT 的作业：计算某个 bm b_m bm 的具体数值！接着便在黑板上写下了 n n n、t t t 的数值，由于 ak a_k ak 实在太多，不能全写在黑板上，老师只给出了一个 ak a_k ak 的递推式，让学生自行计算 ak a_k ak：
ak={(1234⋅ak−1+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<n≤103000,0≤t≤10000,0≤n−m≤5。