← 返回题目列表

AtCoder · m_solutions2019_e

E. 算术级数的乘积

中文机器翻译题面 查看原题

分数: 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.