分数: 600 点
问题陈述
考虑以下算术级数 n 条款:
- x, x + d, x + 2d, \ldots, x + (n-1)d
该序列中所有项的乘积是多少? 计算答案的模数 1\ 000\ 003.
你被给予 Q 此表格的查询。 在 i-th 查询,计算情况下的答案 x = x_i, d = d_i, n = n_i.
约束
- 1 \leq Q \leq 10^5
- 0 \leq x_i, d_i \leq 1\ 000\ 002
- 1 \leq n_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
Q x_1 d_1 n_1 : x_Q d_Q n_Q
输出
打印 Q 行。
在 i第行,打印答案 i- 第一个查询。
示例输入 1
2 7 2 4 12345 67890 2019
示例输出 1
9009 916936
对于第一个查询,答案是 7 \times 9 \times 11 \times 13 = 9009。 不要忘记对答案进行模计算 1\ 000\ 003.