C1274 [CQOI2015]多项式

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

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

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

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

样例输入 1

3
2
2

样例输出 1

10536