题目描述

你在网上闲逛的时候，发现有文章提到等差数列。 你知道求和是简单的，但你不禁好奇求其乘积会怎样？ 所以你需要解决以下问题：给定一个等差数列，求它的各项乘积，你只需要输出其对1145141取模的结果。 具体的，每组给定d,n,a分别表示公差，长度，首项，你需要求出

注意，本题有多组测试数据。

输入格式

第一行共一个整数T表示测试数据组数。 对于每组测试数据，输入一行三个整数表示d,n,a。

输出格式

输出共T行，第i行表示第i组测试数据的结果。 【样例输入1】

2
1 1234 2
2 9876 7

【样例输出1】

809572
177562

【样例输入2】

5
19191 787874 1616
11111 111111 0
11 23 45
0 1 0
1 1145141 1

【样例输出2】

0
0
224427
0
0

数据范围与提示

对于所有数据，满足$0≤d,a≤10^9,1≤n≤10^9,1≤T≤10^5$。 每个测试点的具体限制见下表：