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):
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools
 
setrecursionlimit(10**7)
 
def input():
  return stdin.readline().strip()
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]
 
MOD = 10**6 + 3
 
fact = [1] * MOD
for i in range(1, MOD):
  fact[i] = (fact[i-1] * i) % MOD
invfact = [0] * MOD; invfact[-1] = pow(fact[-1], MOD-2, MOD)
for i in range(MOD-2, -1, -1):
  invfact[i] = invfact[i+1] * (i+1) % MOD

 
def inv(n):
  return pow(n, MOD-2, MOD)
 
def solve(x, d, n):
  if x == 0:
    return 0
  if d == 0:
    return pow(x, n, MOD)
  k = x * inv(d) % MOD
  if n + k - 1 >= MOD:
    return 0
  return fact[n + k - 1] * invfact[k-1] % MOD * pow(d, n, MOD) % MOD
 
Q = read()
for _ in range(Q):
  x, d, n = reads()
  ans = solve(x, d, n)
  print(ans)

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

fact_memo = [0]*mod
fact_memo[0] = 1
for n in range(mod-1):
    fact_memo[n+1] = (n+1)*fact_memo[n]%mod

def fact(n):
    if n>=mod:
        return 0
    else:
        return fact_memo[n]

def inv(n):
    n %= mod
    return pow(n,mod-2,mod)

def cal(x,d,n):
    if x == 0:
        print(0)
        return
    if d == 0:
        print(pow(x,n,mod))
        return
    ans = pow(d,n,mod)
    y = x*inv(d)%mod
    ans *= fact(y+n-1)
    ans %= mod
    ans *= inv(fact(y-1))
    ans %= mod
    print(ans)

for i in range(Q):
    cal(*map(int,input().split()))

Solution (Python):
class Combination:
    '''
    計算量：階乗・逆元テーブルの作成O(N)
            nCkを求めるO(1)
    '''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

q = int(input())
MOD = 10**6 + 3
comb = Combination(MOD, MOD)
for i in range(q):
    a1, d, n = map(int, input().split())
    if d == 0:
        print(pow(a1, n, MOD))
        continue
    syoko = a1 * (comb.inv_fact[d] * comb.fact[d-1])
    syoko %= MOD
    if syoko ==0 or syoko + (n-1) >= MOD:
        print(0)
    else:
        ans = pow(d, n, MOD) * comb.fact[syoko+(n-1)] * comb.inv_fact[syoko-1]
        print(ans % MOD)

Solution (Python):
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)








def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)


def modinv(x,p):
    return pow(x,p-2,p)


def modinv2(x,p):
    g,a,b = exgcd(x,p)  
    return a%p


R = 1000003
facts = [1] * R
for i in range(2,R):
    facts[i] = (facts[i-1]*i)%R

qq = inn()
for q in range(qq):
    x,d,n = inm()
    if d==0:
        print(pow(x,n,R))
        continue
    xd = modinv(d,R)
    y = (x * xd) % R
    if y+n-1 >= R:
        print(0)
    else:
        z = pow(d,n,R) * facts[y+n-1] * modinv(facts[y-1],R)
        print(z%R)

Solution (Python):
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


Max = mod

fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod


Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow(x,n,mod)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n,mod)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))

Solution (Python):
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline 
    INF = 10 ** 25
    mod = 1000003
    Q = int(file())
    ans = ""
    nfact = [1] * mod
    nrev = [1] * mod
    for i in range(2, mod):
        nfact[i] = (nfact[i-1] * i) % mod
    nrev[mod - 1] = pow(nfact[mod - 1], mod - 2, mod)
    for i in reversed(range(1, mod - 1)):
        nrev[i] = (nrev[i+1] * (i + 1)) % mod
    ans = ""
    for i in range(Q):
        x, d, n = map(int, file().split())
        if d == 0: ans += str(pow(x, n, mod)) + "\n"
        else:
            k = (x * nfact[d-1] * nrev[d]) % mod
            if k + n > mod: ans += "0\n"
            elif k == 0: ans += str((pow(d, n, mod) * nfact[n-1]) % mod) + "\n"
            else:
                f = (pow(d, n, mod) * nfact[k + n - 1] * nrev[k - 1]) % mod
                ans += str(f) + "\n"

    print(ans)

    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()
    print(180*(n-2))
    return


def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return


def C():
    return


def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    s = f[0][1]
    c = LI()
    c.sort(key = lambda x:-x)
    f[0][0] = c[0]
    q = deque()
    q.append(s)
    bfs = [1 for i in range(n)]
    f.sort(key = lambda x:x[1])
    bfs[s] = 0
    k = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                f[y][0] = c[k]
                k += 1
                q.append(y)
    ans = 0
    q.append(s)
    bfs = [1 for i in range(n)]
    bfs[s] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return


def E():
    mod = 1000003
    f = [None for i in range(2*mod+1)]
    f[0] = 1
    for i in range(2*mod):
        f[i+1] = (i+1)*f[i]%mod
    inv_f = [0 for i in range(2*mod+1)]
    inv_f[mod-1] = pow(f[mod-1],mod-2,mod)
    for i in range(mod-1)[::-1]:
        inv_f[i] = inv_f[i+1]*(i+1)%mod
    q = I()
    for _ in range(q):
        x,d,n = LI()
        if x == 0:
            print(0)
        elif d == 0:
            print(pow(x,n,mod))
        elif n >= mod:
            print(0)
        else:
            ans = pow(d,n,mod)
            x *= pow(d,mod-2,mod)
            x %= mod
            ans *= f[x+n-1]*inv_f[x-1]%mod
            ans %= mod
            print(ans)
    return


def F():
    n = I()
    return


if __name__ == "__main__":
    E()

Solution (Python):
import sys
input=sys.stdin.readline
mod=1000003
m=mod-1
def modinv(n):
    return pow(n,mod-2,mod)
Fact=[1]
for i in range(1,m+1):
    Fact.append(Fact[i-1]*i%mod)
Finv=[0]*(m+1)
Finv[-1]=modinv(Fact[-1])
for i in range(m-1,-1,-1):
    Finv[i]=Finv[i+1]*(i+1)%mod

def query(x,d,n):
    if x==0:
        return 0
    if d==0:
        return pow(x,n,mod)
    k=(x*modinv(d))%mod
    if k+n-1>=mod:
        return 0
    ans=Fact[k+n-1]*Finv[k-1]%mod
    ans*=pow(d,n,mod)
    ans%=mod
    return ans

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

Solution (Python):
import sys
Q = int(input())
mod = 1000003
frac = [1]*1000003
for i in range(2,1000003):
    frac[i] = i * frac[i-1]%mod
for _ in range(Q):
    x, d, n = map(int, sys.stdin.readline().split())
    p = pow(d, mod-2, mod)*x % mod
    if d == 0:
        print(pow(x, n, mod))
        continue
    elif x == 0:
        print(0)
        continue
    elif p == 0:
        print(0)
        continue
    elif p + n - 1 >= mod:
        print(0)
        continue
    
    print(frac[p+n-1]*pow(frac[p-1], mod-2, mod)*pow(d, n, mod)%mod)

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

def inv_mod(a):
  return pow(a,MOD-2,MOD)

U = MOD + 10

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

Q = int(input())
XDN = [[int(x) for x in input().split()] for _ in range(Q)]

def F(x,d,n):
  if d == 0:
    return pow(x,n,MOD)
  k = inv_mod(d)
  
  
  y = (k*x)%MOD
  if y == 0:
    return 0
  z = y+n-1
  if z >= MOD:
    return 0
  
  result = fact[z]
  result *= inv_mod(fact[y-1])
  result %= MOD
  
  result *= pow(d,n,MOD)
  result %= MOD
  return result

for x,d,n in XDN:
  print(F(x,d,n))

Solution (Python):
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

setrecursionlimit(10**7)

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

MOD = 10**6 + 3

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


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

def solve(x, d, n):
  if x == 0:
    return 0
  if d == 0:
    return pow(x, n, MOD)
  k = x * inv(d) % MOD
  if n + k - 1 >= MOD:
    return 0
  return fact[n + k - 1] * invfact[k-1] % MOD * pow(d, n, MOD) % MOD

Q = read()
for _ in range(Q):
  x, d, n = reads()
  ans = solve(x, d, n)
  print(ans)

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)
    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)))