Problem:
 Score : 600 points    Problem Statement Consider the following arithmetic progression with n terms:   x, x + d, x + 2d, \ldots, x + (n-1)d   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 .      Constraints  1 \leq Q \leq 10^5  0 \leq x_i, d_i \leq 1\ 000\ 002  1 \leq n_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  Q  x_1  d_1  n_1  :  x_Q  d_Q  n_Q       Output Print Q lines.  In the i -th line, print the answer for the i -th query.        Sample Input 1 2
7 2 4
12345 67890 2019      Sample Output 1 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 .

Solution (Python):




import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 6 + 3
modpow = lambda a, n, p = MOD: pow(a, n, p)






def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


    
    
    
    
    
    
    
    
    
    




input2 = lambda: sys.stdin.readline().strip()
r = sys.stdin.readline 
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]


fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))

Solution (Python):




import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 6 + 3
modpow = lambda a, n, p = MOD: pow(a, n, p)






def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


    
    
    
    
    
    
    
    
    
    




input2 = sys.stdin.readline
r = sys.stdin.readline 
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]


fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))

Solution (Python):




import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 6 + 3
modpow = lambda a, n, p = MOD: pow(a, n, p)






def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


    
    
    
    
    
    
    
    
    
    




input2 = sys.stdin.readline
r = sys.stdin.readline 
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]


fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

q = int(input())
mod = 10**6+3
f = {}
f[0] = 1
for i in range(1,mod):
	f[i] = f[i-1] * i % mod

for i in range(q):
	x,d,n = m()
	if d == 0:
		ans = pow(x,n,mod)
	else:
		x = x * pow(d,mod-2,mod)%mod
		if mod <= x + n - 1:
			ans = 0
		else:
			ans = pow(d,n,mod) * f[x+n-1] * pow(f[x-1],mod-2,mod) % mod
	print(ans)

Solution (Python):




import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 6 + 3
def modpow(a, n, p = MOD):
    if   n == 0     : return 1
    elif n == 1     : return a % p
    elif n % 2 == 0 : return modpow(a, n//2, p)**2 % p
    else            : return modpow(a, n//2, p)**2 * a % p
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


    
    
    
    
    
    
    
    
    
    




input2 = sys.stdin.readline
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]


fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n, MOD))
    else:
        x = moddiv(x, d, MOD)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1], MOD),modpow(d, n, MOD), MOD))

Solution (Python):




import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 6 + 3
def modpow(a, n, p = MOD):
    if   n == 0     : return 1
    elif n == 1     : return a % p
    elif n % 2 == 0 : return modpow(a, n//2, p)**2 % p
    else            : return modpow(a, n//2, p)**2 * a % p
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


    
    
    
    
    
    
    
    
    
    




input2 = sys.stdin.readline
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]


fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))

Solution (Python):
Q = int(input())
xdn = [[int(i) for i in input().split()] for _ in range(Q)]

MOD = 10 ** 6 + 3

fact = [0] * MOD
inv = [0] * MOD
fact[0] = 1
inv[0] = pow(fact[0], MOD - 2, MOD)

for i in range(1, MOD) :
    fact[i] = (i * fact[i - 1]) % MOD
    inv[i] = pow(fact[i], MOD - 2, MOD)

for x, d, n in xdn :
    if x == 0 :
        print(0)
        continue
        
    if d == 0 :
        print(pow(x, n, MOD))
        continue
    
    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd + n - 1 >= MOD :
        print(0)
        continue
        
    print((fact[xd + n - 1] * inv[xd - 1] * pow(d, n, MOD)) % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
q = int(input())

p=1000003

fdict={}
fdict[0]=1
for i in range(1,p):
    fdict[i]=fdict[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*fdict[x+n-1]*pow(fdict[x-1],p-2,p)%p
  print(ans%p)

Solution (Python):
import sys
input = sys.stdin.readline
q = int(input())

p=1000003

flist=[1 for i in range(p)]
for i in range(1,p):
    flist[i]=flist[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)

Solution (Python):
import sys
input = sys.stdin.readline
mod=10**6+3

MUL=[1]
for i in range(1,mod):
    MUL.append(MUL[-1]*i%mod)

Q=int(input())
for i in range(Q):
    x,d,n=map(int,input().split())

    if d==0:
        print(pow(x,n,mod))
        continue
    start=x*pow(d,mod-2,mod)%mod
    if start+n-1>=mod:
        print(0)
    else:
        print(MUL[start+n-1]*pow(MUL[start-1],mod-2,mod)%mod*pow(d,n,mod)%mod)

Solution (Python):

Q = int(input())
x, d, n = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), (), ())
)

MOD = 1000003


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))




f = [0 for _ in range(MOD)]
f[0] = ModInt(1)
for i in range(1, MOD):
    f[i] = i * f[i - 1]


def q(X, D, N):
    Y = (
        0 if D.x == 0 else
        X / D
    )
    return (
        X**N if D.x == 0 else
        D**N * f[Y.x + N - 1] / f[Y.x - 1] if Y.x + N - 1 < MOD else
        0
    )


ans = '\n'.join(
    str(q(X, D, N))
    for X, D, N in zip(map(ModInt, x), map(ModInt, d), n)
)


print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return map(int, input().split())


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


M = 1000003
m = Mod(M)
C = Combination(M-1, M)


def slv(x, d, n):
    if d == 0:
        return m.pow(x, n)

    xd = m.div(x, d)
    if n > M - xd:
        return 0

    return m.mul(m.mul(C.g1[xd+n-1], C.g2[xd-1]), m.pow(d, n))


def main():
    Q = read_int()
    for _ in range(Q):
        x, d, n = read_int_n()
        print(slv(x, d, n))


if __name__ == '__main__':
    main()

Solution (Python):
M=10**6+3
Q=int(input())
xdn=list(list(map(int,input().split())) for _ in range(Q))
factorial_list=[1]
for i in range(1,M):
    factorial_list.append(factorial_list[i-1]*i%M)
for x,d,n in xdn:
    t=x*pow(d,M-2,M)%M
    if d==0:
        print(pow(x,n,M))
    elif t+n<=M:
        print(factorial_list[t+n-1]
              *pow(factorial_list[t-1],M-2,M)
              *pow(d,n,M)%M)
    else:
        print(0)

Solution (Python):
import sys


def inpl(): return list(map(int, input().split()))
Q = int(input())
 
MOD = 10**6 + 3
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
size = MOD + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] 
g2[:2] = [1, 1] 
inverse[:2] = [0, 1] 

for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

for _ in range(Q):
    x, d, n = inpl()
    xd = x*inverse[d]%MOD
    if d != 0:
        if n < ((MOD-x)*inverse[d] + 1)%MOD:
            n = n%MOD
            print((g1[(xd + n - 1)%MOD] * g2[(xd-1)%MOD] * pow(d, n, MOD))%MOD)
        else:
            print(0)
    else:
        print(pow(x, n, MOD))

Solution (Python):
class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L
  def invN(s, n):
    L = [0, 1]
    for i in range(2, n):
      L.append(s.MOD - L[s.MOD % i] * (s.MOD // i) % s.MOD)
    return L

Q = int(input())
xdn = [list(map(int, input().split())) for _ in range(Q)]

MOD = 1000003
inv = Inv(MOD)

L = [1] * MOD
IL = [1] * MOD
for i in range(1, MOD):
  L[i] = L[i - 1] * i % MOD
  IL[i] = inv.invx(L[i])

for x, d, n in xdn:
  if d == 0:
    print(inv.modpow(x, n))
    continue

  id = inv.invx(d)
  k = x * id % MOD
  if k + n > MOD:
    print(0)
    continue
  t = inv.modpow(d, n)
  print(L[k + n - 1] * IL[k - 1] * t % MOD)

Solution (Python):
MOD = 1000003
MAX = MOD
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0:
    return 0
  return (((fact[n]*invfact[k])%MOD)*invfact[n-k])%MOD

comb_build(MAX)

q = int(input())
for i in range(q):
  x, d, n = list(map(int, input().split()))
  if x==0 or d==0:
    print(pow(x, n, MOD))
    continue

  x = x*pow(d, MOD-2, MOD)%MOD
  if x+n-1>=MOD:
    print(0)
  else:
    ans = pow(d, n, MOD)*fact[x+n-1]*invfact[x-1]%MOD
    print(ans)

Solution (Python):
p,M=pow,1000003
f=[1]*M
for i in range(1,M):f[i]=f[i-1]*i%M
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print[p(x,n,M),M/(t+n)and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0]

Solution (Python):
p,M=pow,1000003
f=[1]*M
for i in range(1,M):f[i]=f[i-1]*i%M
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print[p(x,n,M),M/(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0]

Solution (Python):
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print[p(x,n,M),M/(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0]

Solution (Python):
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print([p(x,n,M),M/(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Solution (Python):
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):x,d,n=map(int,input().split());t=x*p(d,M-2,M)%M;print([p(x,n,M),M//(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Solution (Python):
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):x,d,n=map(int,input().split());t=x*p(d,M-2,M)%M;print([p(x,n,M),(M-n>=t>0)*1and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Solution (Python):
M,f=1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):x,d,n=map(int,input().split());t=x*pow(d,M-2,M)%M;print([pow(x,n,M),(M-n>=t>0)*1and f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M][d>0])

Solution (Python):
M=1000003
f=[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):
	x,d,n=map(int,input().split())
	t=x*pow(d,M-2,M)%M
	print([pow(x,n,M),(M-n>=t>0)*1and f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M][d>0])

Solution (Python):
M=1000003
f=[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):
	x,d,n=map(int,input().split())
	t=x*pow(d,M-2,M)%M
	print([pow(x,n,M),M-n>=t>0and f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M or 0][d>0])

Solution (Python):
M=1000003
f=[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):
	x,d,n=map(int,input().split())
	t=x*pow(d,M-2,M)%M
	if d==0:
		print(pow(x,n,M))
	elif 0<t<=M-n:
		print(f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M)
	else:
		print(0)

Solution (Python):
M=1000003
f=[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):
	x,d,n=map(int,input().split())
	t=x*pow(d,M-2,M)%M
	if d==0:
		print(pow(x,n,M))
	elif t==0 or t+n>M:
		print(0)
	else:
		print(f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M)

Solution (Python):
M=1000003
f=[1]
for i in range(1,M):
	f.append(f[i-1]*i%M)
Q=int(input())
for _ in'_'*Q:
	x,d,n=map(int,input().split())
	if d==0:
		print(pow(x,n,M))
	else:
		t=x*pow(d,M-2,M)%M
		if t==0 or t+n-1>=M:
			print(0)
		else:
			print(f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M)

Solution (Python):
mod = 10 ** 6 + 3

W = [1] * (mod)
for i in range(mod - 1):
	W[i + 1] = ((i + 1) * W[i]) % mod

def rev(a):
	return pow(a, mod - 2, mod)

def f(x, d, n):
	if d == 0:
		return pow(x, n, mod)
	else:
		d_r = rev(d)
		xdr = d_r * x % mod
		if xdr == 0:
			return 0
		elif (xdr + n - 1) >= mod:
			return 0
		else:
			return (W[xdr + n - 1] * rev(W[xdr - 1]) % mod) * pow(d, n, mod) % mod

ans = []
q = int(input())
for _ in range(q):
    x,d,n = map(int,input().split())
    ans.append(f(x,d,n))
for i in ans:
    print(i)

Solution (Python):
mod = 10 ** 6 + 3

W = [1]
for i in range(1, mod):
	W.append((W[-1] * i) % mod)

def rev(a):
	return pow(a, mod - 2, mod)

def f(x, d, n):
	if d == 0:
		return pow(x, n, mod)
	else:
		d_r = rev(d)
		xdr = d_r * x % mod
		if xdr == 0:
			return 0
		elif (xdr + n - 1) >= mod:
			return 0
		else:
			return (W[xdr + n - 1] * rev(W[xdr - 1]) % mod) * pow(d, n, mod) % mod

Q = int(input())
for i in range(Q):
	x, d, n = map(int, input().split())
	print(f(x, d, n))

Solution (Python):
mod = 10 ** 6 + 3

W = [1] * (mod)
for i in range(mod - 1):
	W[i + 1] = ((i + 1) * W[i]) % mod

def rev(a):
	return pow(a, mod - 2, mod)

def f(x, d, n):
	if d == 0:
		return pow(x, n, mod)
	else:
		d_r = rev(d)
		xdr = d_r * x % mod
		if xdr == 0:
			return 0
		elif (xdr + n - 1) >= mod:
			return 0
		else:
			return (W[xdr + n - 1] * rev(W[xdr - 1]) % mod) * pow(d, n, mod) % mod

Q = int(input())
for i in range(Q):
	x, d, n = map(int, input().split())
	print(f(x, d, n))

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**6 + 3

    factrial = [1] * (MOD)
    for k in range(1, MOD):
        factrial[k] = (factrial[k-1] * k) % MOD
    
    fact_inv = [1] * (MOD)
    fact_inv[MOD-1] = pow(factrial[MOD-1], MOD - 2, MOD)
    for k in range(MOD-2, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    Q = int(input())
    for _ in range(Q):
        x, d, n = map(int, input().split())

        if d == 0:
            ans = pow(x, n, MOD)

        else:
            y = x * pow(d, MOD-2, MOD) % MOD

            if y + n - 1 >= MOD:
                ans = 0

            else:
                ans = (factrial[y+n-1] * fact_inv[y-1] * pow(d, n, MOD)) % MOD

        print(ans)


if __name__ == '__main__':
    main()