题目描述

原件：tmp.png

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

$$\sum^n_{k=0}a_k x^k=\sum^n_{k=0}b_k(x-t)^k$$

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

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

输入格式

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

输出格式

输出一行，为$N$的值。

样例

3
2
2

10536

数据范围与约定

对于$100\%$的数据，$0<n≤103000，0≤t≤10000，0≤n-m≤5$.