题目背景

你说得对，但是 $\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$。

每个测试点的具体限制见下表：

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$