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.



Sample input:
2
7 2 4
12345 67890 2019


Sample output:
9009
916936

Submission status: Runtime Error

Solution code:
mod = 1000003
"""
for i in range(2,57000):
    if n%i==0:
        print("nonPrime")
        exit()
print("prime")
"""
q = int(input())
fct = [0]
tmp = 1
for i in range(1,mod):
    tmp *=i
    tmp%=mod
    fct.append(tmp)
for i in range(q):
    x,d,n = map(int, input().split( ))
    if d%mod == 0:
        print(pow(x,mod-2,mod))
        continue
    if n>=mod:
        print(0)
        continue
    rev_d = pow(d,mod-2,mod)
    x*=rev_d
    x%=mod
    tmp = pow(d,n,mod)
    tmp*=fct[x+n-1]
    if x>=1:
        tmp*=pow(fct[x-1],mod-2,mod)
    tmp%=mod
    print(tmp)

Submission status: Runtime Error

Solution code:
from collections import *
mod=10**6+3
fac=[0 for i in range(mod)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
fac[0]=0
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a=(x-d%mod)*D%mod
    b=a+n
    if a<b:
        if a>0:
            value=fac[b]*pow(fac[a],mod-2,mod)*pow(d,n,mod)
        else:
            value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from collections import *
mod=10**6+3
fac=[0 for i in range(mod-1)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a,b=x*D%mod,(x+(n-1)*d)*D%mod
    if d>5:
        if a>=0 and a<b and b<mod-1:
            if a>0:
                value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
            elif a==0:
                value=fac[b]*pow(d,n,mod)
            print(value%mod)
        else:
            print(0)
    else:
        print(unko)

Submission status: Runtime Error

Solution code:
from collections import *
mod=10**6+3
fac=[0 for i in range(mod-1)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a>=0 and a<b and b-1<mod:
        if a>0:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        elif a==0:
            value=fac[b]*pow(d,n,mod)

        print(value%mod)

    else:
        print(0)

Submission status: Runtime Error

Solution code:
from collections import *
mod=10**6+3
fac=[0 for i in range(mod-1)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a>0 and a<b and b-1<mod:
        value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from collections import *
mod=10**6+3
fac=[0 for i in range(mod-1)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a>0 and a<b and b<mod:
        value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
from collections import *
mod=10**6+3
fac=[0 for i in range(mod-1)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a,b=x*D%mod,(x+(n-1)*d)*D%mod
    print(a,b)
    if a>0 and a<b and b<mod:
        value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
mod=10**6+3

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

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

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

for x,d,n in xdn:
    k=x*inv[d]%mod
    if k+n-1>=mod:
        print(0)
    else:
        print(pow(d,k+n-1,mod)*data[k+n-1]*inv[pow(d,k-1,mod)*data[k-1]%mod]%mod)

Submission status: Runtime Error

Solution code:

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]
    mod = 10 ** 6 + 3

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

    for i in range(num):
        x, d, n = data[i]
        if d == 0:
            ans = pow(x, n, mod)
        else:
            t = x * pow(d, mod - 2, mod)
            t %= mod
            ans = origin[t + n - 1] * pow(origin[t - 1], mod - 2, mod)
            ans %= mod
            ans *= pow(d, n, mod)
            ans %= mod
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
q = int(input())
for _ in range(q):
    x, d, n = map(int, input().split())
    ans = x
    for i in range(d, n*d, d):
        ans = ans * (x + i) % 1000003
    print(ans)

Submission status: Runtime Error

Solution code:
Q = int(input())
div = 1000003
div_2 = div/2
for _ in range(Q):
  x, d, n = map(int, input())
  q = 1
  for i in range(1, n+1):
    tmp = (x + d*(i-1)) % div
    if tmp > div_2:
      tmp -= div
    q *= tmp
  if q < 0:
    q += div
  print(q)

Submission status: Runtime Error

Solution code:
Q = int(input())
div = 1000003
div_2 = div/2
for _ in range(Q):
    x, d, n = map(int, input())
    q = 1
    for i in range(1, n+1):
      tmp = (x + d*(i-1)) % div
      if tmp > div_2:
        tmp -= div
      q *= tmp
    if q < 0:
      q += div
    print(q)

Submission status: Runtime Error

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
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
    lambda a, n: pow(a, n, p = MOD)
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

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

# calculate
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)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Runtime Error

Solution code:
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 = m()
mod = 10**6+3
f = {}
f[0] = 1
for i in range(1,p):
	f[i] = d[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)

Submission status: Runtime Error

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
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):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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 = [1]
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l.append(tmp)
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

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

# calculate
fac_list = modfactorial_list(MOD*2)
for (x, d, n) in xdn:
    x = moddiv(x, d)
    print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Runtime Error

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
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):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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 = [1]
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l.append(tmp)
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

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

# calculate
fac_list = modfactorial_list(MOD)
for (x, d, n) in xdn:
    x = moddiv(x, d)
    print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Runtime Error

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
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):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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 = [1]
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l.append(tmp)
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

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

# calculate
fac_list = modfactorial_list(MOD)
for (x, d, n) in xdn:
    x = moddiv(x, d)
    print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Runtime Error

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
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):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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 = [1]
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l.append(tmp)
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

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

# calculate
fac_list = modfactorial_list(MOD)
for (x, d, n) in xdn:
    x = moddiv(x, d)
    print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Runtime Error

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

p=1000003

flist=[1 for i in range(p)]
flist[0]=1
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)
  elif p<=x+n-1:
    ans=0
  else:
    x=x*pow(d,p-2,p)%p
    ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)

Submission status: Runtime Error

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

p=1000003

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % p
    elif y % 2 == 0 : return power(x, y//2)**2 % p
    else            : return power(x, y//2)**2 * x % p
    
factorial_list=[1 for i in range(p)]
for i in range(1,p):
    factorial_list[i]=factorial_list[i-1]*i%p
    
inv_list=[1 for i in range(p)]
inv_list[-1]=factorial_list[-1]
for i in range(p-1,1,-1):
    inv_list[i-1]=inv_list[i]*i%p
    
for i in range(q):
    x,d,n=(int(i) for i in input().split())
    if d%p==0:
        ans=power(x,n)
        print(ans%p)
    elif x<=p*d<=x+(n-1)*d or x==0:
        print(0)
    else:
        x=x*power(d,p-2)%p
        ans=factorial_list[x+n-1]*inv_list[x-1]*power(d,n)
        print(ans%p)

Submission status: Runtime Error

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

p=1000003

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % p
    elif y % 2 == 0 : return power(x, y//2)**2 % p
    else            : return power(x, y//2)**2 * x % p
    
factorial_list=[1 for i in range(p)]
for i in range(1,p):
    factorial_list[i]=factorial_list[i-1]*i%p
    
inv_list=[1 for i in range(p)]
inv_list[-1]=factorial_list[-1]
for i in range(p-1,1,-1):
    inv_list[i-1]=inv_list[i]*i%p
    
for i in range(q):
    x,d,n=(int(i) for i in input().split())
    if d%p==0:
        ans=power(x,n)
        print(ans%p)
    elif x<=p*d<=x+(n-1)*d:
        print(0)
    else:
        x=x*power(d,p-2)%p
        ans=factorial_list[x+n-1]*inv_list[x-1]*power(d,n)
        print(ans%p)