{"raw_statement":[{"iden":"problem statement","content":"Consider the following arithmetic progression with $n$ terms:\n\n*   $x, x + d, x + 2d, \\ldots, x + (n-1)d$\n\nWhat is the product of all terms in this sequence? Compute the answer modulo $1\\ 000\\ 003$.\nYou 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$."},{"iden":"constraints","content":"*   $1 \\leq Q \\leq 10^5$\n*   $0 \\leq x_i, d_i \\leq 1\\ 000\\ 002$\n*   $1 \\leq n_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$Q$\n$x_1$ $d_1$ $n_1$\n$:$\n$x_Q$ $d_Q$ $n_Q$"},{"iden":"sample input 1","content":"2\n7 2 4\n12345 67890 2019"},{"iden":"sample output 1","content":"9009\n916936\n\nFor 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$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}