Score : 600 points
Consider the following arithmetic progression with n terms:
What is the product of all terms in this sequence? Compute the answer modulo 1\ 000\ 003.
You are given Q queries of this form. In the i-th query, compute the answer in case x = x_i, d = d_i, n = n_i.
Input is given from Standard Input in the following format:
Q x_1 d_1 n_1 : x_Q d_Q n_Q
Print Q lines.
In the i-th line, print the answer for the i-th query.
2 7 2 4 12345 67890 2019
9009 916936
For the first query, the answer is 7 \times 9 \times 11 \times 13 = 9009. Don't forget to compute the answer modulo 1\ 000\ 003.