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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 6 + 3



def init_fact_inv(MAX: int, MOD: int) -> list:
    
    factorial = [1] * MAX
    factorial[0] = factorial[1] = 1
    for i in range(2, MAX):
        factorial[i] = factorial[i-1] * i % MOD
    
    inverse = [1] * MAX
    
    inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
    for i in range(MAX-2, 0, -1):
        
        inverse[i] = inverse[i+1] * (i+1) % MOD
    return factorial, inverse

fact, inv = init_fact_inv(MOD, MOD)

Q=INT()
for i in range(Q):
    x,d,n=MAP()

    
    if x==0:
        print(0)
        continue
    if d==0:
        print(pow(x, n, MOD))
        continue
    
    invd=pow(d, MOD-2, MOD)
    l=(x*invd-1)%MOD
    r=l+n

    
    if r>=MOD:
        print(0)
        continue

    print(fact[r]*inv[l]*pow(d, n, MOD)%MOD)

Solution (Python):

def PoAP_fnct(MOD):
    
    fact_mod = [1,1]
    inv_mod = [0,1]
    inv_fact_mod = [1,1]
    i = len(fact_mod)
    i_ = len(inv_fact_mod)

    def PoAP(x,d,n):
        nonlocal i, i_
        if d == 0:
            return pow(x,n%(MOD-1),MOD)

        while d >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        j = (-x*inv_mod[d])%MOD
        if j < n:
            return 0

        x = (x*inv_mod[d])%MOD

        while (x+n-1)%MOD >= i:
            fact_mod[i:i] = [(fact_mod[i-1]*i)%MOD]
            i += 1

        while x-1 >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        return fact_mod[(x+n-1)%MOD] * inv_fact_mod[x-1] * pow(d,n%(MOD-1),MOD) % MOD
    return PoAP

def solve():
    Q = int(input())
    PoAP = PoAP_fnct(1000003)
    res = '\n'.join([str(PoAP(*map(int, input().split()))) for _ in range(Q)])
    return str(res)

if __name__ == '__main__':
    print(solve())

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

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

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:
            if x_div+n-1 >= MOD:
                ans = 0
            else:
                ans = fact[x_div+n-1]*finv[x_div-1]%MOD*pow(d, n, MOD)%MOD
    print(ans)

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

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

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:
            if x_div+n-1 >= MOD:
                ans = 0
            else:
                f = fact[x_div+n-1]
                fi = pow(fact[x_div-1], MOD-2, MOD)
                ans = f*fi%MOD*pow(d, n, MOD)%MOD
    print(ans)

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

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

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:

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

Solution (Python):
q = int(input())
Q = [[int(i) for i in input().split()] for j in range(q)]
p = 10 ** 6 + 3

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(p - 1, p)
invf = invfact(p - 1, f, p)

for x, d, n in Q:
    if d == 0:
        print(pow(x, n, p))
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)
    x_over_d = x * inv_d % p

    if x_over_d == 0 or x_over_d + n - 1 >= p:
        print(0)
        continue

    print(d_n * f[x_over_d + n - 1] * invf[x_over_d - 1] % p)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 1000003
q = int(input())
cumprod = [1]
for i in range(1, MOD):
	cumprod.append((cumprod[-1] * i) % MOD)

def calc(l, r):
	return (cumprod[r] * pow(cumprod[l-1], MOD-2, MOD)) % MOD

def solve(x, d, n):
	if x == 0:
		return 0
	elif d == 0:
		return pow(x, n, MOD)
	else:
		l = (x * pow(d, MOD-2, MOD)) % MOD
		if l+n-1 >= MOD:
			return 0
		else:
			return (calc(l, l+n-1) * pow(d, n, MOD)) % MOD

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

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 1000003
q = int(input())
cumprod = [1]
for i in range(1, MOD):
	cumprod.append((cumprod[-1] * i) % MOD)

def calc(l, r):
	return (cumprod[r] * pow(cumprod[l-1], MOD-2, MOD)) % MOD

def solve(x, d, n):
	if x == 0:
		return 0
	elif d == 0:
		return pow(x, n, MOD)
	else:
		l = (x * pow(d, MOD-2, MOD)) % MOD
		if l+n-1 >= MOD:
			return 0
		else:
			return (calc(l, l+n-1) * pow(d, n, MOD)) % MOD

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

Solution (Python):
MOD = 1000003
q = int(input())
cumprod = [1]
for i in range(1, MOD):
	cumprod.append((cumprod[-1] * i) % MOD)

def calc(l, r):
	return (cumprod[r] * pow(cumprod[l-1], MOD-2, MOD)) % MOD

def solve(x, d, n):
	if x == 0:
		return 0
	elif d == 0:
		return pow(x, n, MOD)
	else:
		l = (x * pow(d, MOD-2, MOD)) % MOD
		if l+n-1 >= MOD:
			return 0
		else:
			return (calc(l, l+n-1) * pow(d, n, MOD)) % MOD

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

Solution (Python):

from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    

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

    if x == 0:
        ans.append(0)
        continue

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

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append(reduce(mod_mul, (fact[xd + n - 1], inv_fact[xd - 1], dn)))
print(*ans, sep='\n')

Solution (Python):

import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3

fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    

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

    if x == 0:
        ans.append(0)
        continue

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

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)
print(*ans, sep='\n')

Solution (Python):

import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3

fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    

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

    if x == 0:
        ans.append(0)
        continue

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

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)
print(*ans, sep='\n')

Solution (Python):

import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3

fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    

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

    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 == 0:
        print(0)
        continue

    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)

Solution (Python):

import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = inv(fact[-1])
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    

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

    if x == 0:
        print(0)
        continue

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

    xd = (x * inv(d)) % MOD
    if xd == 0:
        print(0)
        continue

    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)

Solution (Python):

from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = inv(fact[-1])
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    

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

    if x == 0:
        print(0)
        continue

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

    xd = (x * inv(d)) % MOD
    if xd == 0:
        print(0)
        continue
        
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)

Solution (Python):

from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = inv(fact[-1])
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    
    
Q = int(input())
for _ in range(Q):
    x, d, n = map(int, input().split())

    if x == 0:
        print(0)
        continue

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

    xd = (x * inv(d)) % MOD
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(reduce(mod_mul, (fact[xd + n - 1], inv_fact[xd - 1], dn)))

Solution (Python):

from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

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

    if x == 0:
        print(0)
        continue

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

    xd = (x * inv(d)) % MOD
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(reduce(mod_mul, (fact[xd + n - 1], inv(fact[xd - 1]), dn)))

Solution (Python):

from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    
    
    
    

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

    if x == 0:
        print(0)
        continue

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

    xd = (x * inv(d)) % MOD
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(reduce(mod_mul, (fact[xd + n - 1], inv(fact[xd - 1]), dn)))

Solution (Python):

from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append(mod_mul(fact[-1], n))
    
    
    
    

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

    if x == 0:
        print(0)
        continue

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

    xd = mod_mul(x, inv(d))
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(mod_mul(mod_mul(fact[xd + n - 1], inv(fact[xd - 1])), dn))

Solution (Python):
mod = 10**6+3
max = 10**6+2
g1 = [1, 1]
for i in range( 2, max + 1 ):
    g1.append( ( g1[-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 (g1[xdr+n-1]*rev(g1[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
n = MOD + 10

fac = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * i % MOD

q = int(input())

def f(x, d, n):
    if d == 0:
        return pow(x, n, MOD)
    p = (x * pow(d, MOD-2, MOD)) % MOD
    if p + n - 1 >= MOD:
        return 0
    q = fac[(p + n - 1) % MOD]
    r = fac[p - 1]
    s = pow(d, n, MOD)
    return (q*pow(r, MOD-2, MOD)*s) % MOD

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

Solution (Python):
class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]


Q = int(input())
items = []
for i in range(Q):
    items.append(tuple(map(int, input().split())))

mod = 10 ** 6 + 3
fact_mod = FactMod(mod - 1, mod)

for x, d, n in items:
    if d == 0:
        print(pow(x, n, mod))
    elif x == 0:
        print(0)
    else:
        
        invd = pow(d, mod - 2, mod)

        
        xd = x * invd % mod

        
        if n - 1 + xd >= mod:
            print(0)
            continue
        
        dn = pow(d, n, mod)
        print(fact_mod.fact(xd + n - 1) * fact_mod.inv[xd - 1] % mod * dn % mod)

Solution (Python):
p=1000003
def inv(x):
    return pow(x,p-2,p)
def exponen(a,b):
    return pow(a,b,p)
Fact=[0 for i in range(p)]
Fact[0]=1
for i in range(p-1):
    Fact[i+1]=((i+1)*Fact[i])%p
def fact(k):
    if 0<=k<p:
        return Fact[k]
    else:
        return 0
def solve(x,d,n):
    if x==0:
        return 0
    if d==0:
        return exponen(x,n)
    a=(x*inv(d))%p
    check=(-a)%p
    if 0<=check<=n-1:
        return 0
    return (exponen(d,n)*(fact(n-1+a)*inv(fact(a-1)))%p)%p

Q=int(input())
for i in range(Q):
    xi,di,ni=map(int,input().split())
    print(solve(xi,di,ni))

Solution (Python):
import math
N = int(input())

g = 1000003

fr = [1] * g
for x in range(2, g):
    fr[x] = x * fr[x-1] % g

def div(a, b):
    return a * pow(b, g-2, g) % g

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

    if d == 0:
        print(pow(x, n, g))

    else:
        s = div(x, d)
        x, y = s+n-1, s-1
        if s+n-1 < g :
            print(div(fr[x], fr[y]) * pow(d, n, g) % g)
        else:
            print(0)

Solution (Python):
import math
N = int(input())

g = 1000003

fr = [1] * g
for x in range(2, g):
    fr[x] = x * fr[x-1] % g

def div(a, b):
    return a * pow(b, g-2, g) % g

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

    if d == 0:
        print(pow(x, n, g))

    else:
        s = div(x, d)
        x, y = s+n-1, s-1
        if s+n-1 < g :
            print(div(fr[x], fr[y]) * pow(d, n, g) % g)
        else:
            print(0)

Solution (Python):
Q = int(input())

mod = 10 ** 6 + 3
table = [1]
for i in range(1, mod):
    table.append(table[-1]*i % mod)

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
    else:
        y = x * pow(d, mod - 2, mod) % mod
        if y + n - 1 >= mod:
            print(0)
        else:
            print(pow(d, n, mod) * table[y + n - 1] * pow(table[y - 1], mod - 2, mod) % mod)

Solution (Python):
class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]

    def comb(self, n, r):
        """
        :return: nCr
        """
        return self.f[n] * self.inv[n - r] * self.inv[r] % self.mod


Q = int(input())
items = []
for i in range(Q):
    items.append(tuple(map(int, input().split())))

mod = 10 ** 6 + 3
fact_mod = FactMod(mod - 1, mod)

for x, d, n in items:
    if d == 0:
        print(pow(x, n, mod))
    elif x == 0:
        print(0)
    else:
        invd = pow(d, mod - 2, mod)

        xd = x * invd % mod
        limit = mod - xd
        if n > limit:
            print(0)
            continue

        r = xd + n - 1
        l = xd - 1
        tmp = pow(d, n, mod)
        print(fact_mod.fact(r) * fact_mod.inv[l] * tmp % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    Q = II()
    query = []
    for _ in range(Q):
        query.append(LI())
    fact = [1] * MOD
    for i in range(1, MOD):
        fact[i] = fact[i - 1] * i % MOD
    ifact = [1] * MOD
    ifact[MOD - 1] = pow(fact[MOD - 1], MOD - 2, MOD)
    for i in range(MOD - 1, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    anss = []
    for x, d, n in query:
        if d == 0:
            ans = pow(x, n, MOD)
        else:
            x = x * pow(d, MOD - 2, MOD) % MOD
            if x + n > MOD or x == 0:
                ans = 0
            else:
                factor = pow(d, n, MOD)
                perm = fact[x + n - 1] * ifact[x - 1] % MOD
                ans = perm * factor % MOD
        anss.append(ans)
    print(*anss, sep='\n')
    return

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    Q = II()
    query = []
    for _ in range(Q):
        query.append(LI())
    fact = [1] * MOD
    for i in range(1, MOD):
        fact[i] = fact[i - 1] * i % MOD
    ifact = [1] * MOD
    ifact[MOD - 1] = pow(fact[MOD - 1], MOD - 2, MOD)
    for i in range(MOD - 1, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    for x, d, n in query:
        if d == 0:
            ans = pow(x, n, MOD)
        else:
            x = x * pow(d, MOD - 2, MOD) % MOD
            if x + n > MOD or x == 0:
                ans = 0
            else:
                factor = pow(d, n, MOD)
                perm = fact[x + n - 1] * ifact[x - 1] % MOD
                ans = perm * factor % MOD
        print(ans)
    return

main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    Q = II()
    query = []
    for _ in range(Q):
        query.append(LI())
    fact = [1] * MOD
    for i in range(1, MOD):
        fact[i] = fact[i - 1] * i % MOD
    ifact = [1] * MOD
    ifact[MOD - 1] = pow(fact[MOD - 1], MOD - 2, MOD)
    for i in range(MOD - 1, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    for x, d, n in query:
        if d == 0:
            ans = pow(x, n, MOD)
        else:
            x = x * pow(d, MOD - 2, MOD) % MOD
            if (x + n - 1) // MOD > (x - 1) // MOD:
                ans = 0
            else:
                factor = pow(d, n, MOD)
                start, end = (x - 1) % MOD, (x + n - 1) % MOD
                perm = fact[end] * ifact[start] % MOD
                ans = perm * factor % MOD
        print(ans)
    return

main()

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

fac = [0]*mod
fac[0] = 1
for i in range(1, mod):
    fac[i] = fac[i - 1] * i
    fac[i] %= mod

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
            ret %= mod
        x *= x
        x %= mod
        n >>= 1
    return ret

l = input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = mod_inv(d, mod)
    x_d = (x * inv_d) % mod
    
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[x_d + n - 1]
    ans2 = fac[x_d - 1]
    
    ans = ans1 * mod_inv(ans2, mod)
    ans %= mod
    d_n = mod_pow(d, n, mod)
    ans = ans * d_n
    ans %= mod
    print(ans)

Solution (Python):



MOD = 1000003


def inv(x, m):
  y, u, v = m, 1, 0

  while y != 0:
    t = x // y
    x -= t * y
    u -= t * v
    x, y = y, x
    u, v = v, u

  return u % m


def main():
  facs = [None] * MOD
  invs = [None] * MOD

  facs[0] = 1
  for i in range(1, MOD):
    facs[i] = facs[i - 1] * i % MOD

  invs[-1] = facs[-1]
  for i in range(MOD - 1, 0, -1):
    invs[i - 1] = invs[i] * i % MOD

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

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

    x = x * inv(d, MOD) % MOD

    if x + n - 1 >= MOD:
      print(0)
      continue

    v = facs[x + n - 1]

    if x != 0:
      v = v * invs[x - 1] % MOD

    if d != 1:
      v = v * pow(d, n, MOD) % MOD

    print(v)


if __name__ == '__main__':
  main()

Solution (Python):
import sys


def prepare(n, MOD):
    facts = [1]
    t = 1
    for i in range(1, n + 1):
        t = t * i % MOD
        facts.append(t)
    invs = [1] * (n + 1)
    t = pow(t, MOD - 2, MOD)
    invs[n] = t
    for i in range(n, 1, -1):
        t = t * i % MOD
        invs[i - 1] = t
    return facts, invs


MOD = 1000003
facts, factinvs = prepare(MOD - 1, MOD)

q = int(input())
ans = []
for line in sys.stdin:
    x, d, n = map(int, line.split())

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

    invd = pow(d, MOD - 2, MOD)

    xd = x * invd % MOD
    limit = MOD - xd

    if n > limit:
        ans.append(0)
        continue

    r = xd + n - 1
    l = xd - 1
    dn = pow(d, n, MOD)
    ans.append(facts[r] * factinvs[l] * dn % MOD)

print('\n'.join(map(str, ans)))

Solution (Python):
Q = int(input())
MOD = 10 ** 6 + 3

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

rfact = [0] * P
rfact[P - 1] = pow(fact[P - 1], MOD - 2, MOD)
for i in range(P - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, MOD))
    else:
        rd = pow(d, MOD - 2, MOD)
        rx = (rd * x) % MOD
        if rx == 0:
            print(0)
        elif rx + n - 1 >= MOD:
            print(0)
        else:
            print((fact[rx + n - 1] * pow(fact[rx - 1], MOD - 2, MOD) * pow(d, n, MOD)) % MOD)

Solution (Python):
Q = int(input())
mod = 10**6+3
arr = []
for i in range(Q):
    arr.append(list(map(int, input().split())))

P = [1]*(mod+1)
for i in range(mod):
    P[i+1] = P[i]*(i+1)%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 (P[xdr+n-1] * rev(P[xdr-1])%mod) * pow(d,n,mod)%mod

for i in range(Q):
    print(f(arr[i][0], arr[i][1], arr[i][2]))

Solution (Python):
Q = int(input())
mod = 10**6+3
arr = []
for i in range(Q):
    x, d, n = map(int, input().split())
    arr.append([x, d, n])

P = [1]*(mod+1)
for i in range(mod):
    P[i+1] = P[i]*(i+1)%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)
        if d_r * x % mod == 0:
            return 0
        elif (d_r*x%mod+n-1) >= mod:
            return 0
        else:
            return (P[d_r*x%mod+n-1] * rev(P[d_r*x%mod-1])%mod)*pow(d,n,mod)%mod

for i in range(Q):
    print(f(arr[i][0], arr[i][1], arr[i][2]))

Solution (Python):
import sys



def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    
    return [w[0], w[1]]



def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


readline = sys.stdin.readline
MOD_NUM = 10**6 + 3

Q = int(readline())
q_array = [list(map(int, readline().split())) for i in range(Q)]
ans_array = []

factorial = [1] * MOD_NUM
factorial_inv = [1] * MOD_NUM

tmp = 1
for i in range(2, MOD_NUM):
    tmp = tmp * i % MOD_NUM
    factorial[i] = tmp
    factorial_inv[i] = mod_inv(tmp, MOD_NUM)

for q in q_array:
    x, d, n = q
    
    if x == 0:
        ans_array.append("0\n")
        continue
    if d == 0:
        ans = pow(x, n, MOD_NUM)
        ans_array.append(str(ans) + "\n")
    else:
        x_start = x * mod_inv(d, MOD_NUM) % MOD_NUM
        if x_start + n > MOD_NUM:
            ans_array.append("0\n")
        else:
            ans = factorial[x_start + n - 1] * factorial_inv[
                x_start - 1] * pow(d, n, MOD_NUM) % MOD_NUM
            ans_array.append(str(ans) + "\n")

sys.stdout.writelines(ans_array)

Solution (Python):
fa = [1]
P = 10**6+3
for i in range(1, P):
    fa.append(fa[-1]*i%P)

for _ in range(int(input())):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, P))
    else:
        y = pow(d, P-2, P) * x % P
        if y+n-1 >= P:
            print(0)
        else:
            print(pow(d, n, P) * fa[y+n-1] * pow(fa[y-1], P-2, P) % P)