题目背景
你说得对，但是 $\text{Surise}$ 是由 zbr 开发的会记录群内成员说过的话然后从中选取进行随机说话的 bot，后面忘了。
题目描述
yzh 觉得 bot 有点有点了，他要考验 bot 的算力，所以他打算给 bot 出一个等差数列问题，然而求和太平凡了，于是他想让你试试求积。
给定 $d,n,a$，求 $$ \prod\limits_{i=0}^{n-1}(a+i\times d) \bmod 1145141 $$
不过为了考验 bot 的算力，给出的 $n \in [0,+\infty)$，并且需要在 $\texttt{1s}$ 内给出答案。
注意，本题有多组测试数据。
输入格式
第一行共一个整数 $T$ 表示测试数据组数。
对于每组测试数据，输入一行三个整数表示 $d,n,a$．
输出格式
输出共 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的结果。
样例1
样例输入1
2 1 1234 2 2 9876 7
样例输出1
809572 177562
样例2
样例输入2
5 19191 787874 1616 11111 111111 0 11 23 45 0 1 0 1 1145141 1
样例输出2
0 0 224427 0 0
样例3
见下发文件，满足 $n< 1145141,d=1$.
数据范围
对于所有数据，满足 $0\leq d,a\leq10^{9},1\leq n\leq 10^9,1\leq T\leq 10^4$。
每个测试点的具体限制见下表：
| 测试点编号 | $n$ | 特殊性质 |
|---|---|---|
| $1 \sim 3$ | $\leq 50$ | 无 |
| $4 \sim 6$ | $< 1145141$ | $d = 1$ |
| $7 \sim 10$ | 无 | 无 |
时间限制：$\texttt{1s}$
空间限制：$\texttt{512MB}$