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: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
import sys


#互いに素なa,bについて、a*x+b*y=1の一つの解
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
    #[x,y]
    return [w[0], w[1]]


# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
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
    # print(x, d, n)
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
# print(invfact[:10])
 
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)

Submission status: Accepted

Solution code:
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()))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

# extended gcd and modinv
# x = y*(x/y) + x%y
#   ->  g = ax+by = a(y*(x/y) + x%y) + by
#         = (a*(x/y) + b)*y + a*(x%y)
#
# while  g=ax+by, b==0  ->  g=x, a=1

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)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    return pow(x,p-2,p)


def modinv2(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    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)

Submission status: Accepted

Solution code:
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
#O(1)で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))

Submission status: Accepted

Solution code:
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 #single: int(file()), line: map(int, file().split())
    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()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

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

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

#C
def C():
    return

#D
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

#E
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

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)
  # k^nをかけると
  # (kx)(kx+1)...(kx+n-1)
  y = (k*x)%MOD
  if y == 0:
    return 0
  z = y+n-1
  if z >= MOD:
    return 0
  # z! / (y-1)!
  result = fact[z]
  result *= inv_mod(fact[y-1])
  result %= MOD
  # 最後にk^nで割る
  result *= pow(d,n,MOD)
  result %= MOD
  return result

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

Submission status: Accepted

Solution code:
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
# print(invfact[:10])

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)

Submission status: Accepted

Solution code:
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)))

Submission status: Runtime Error

Solution code:
m=1000003
r=range
inv=[0,1]
for i in r(2,m):inv+=[(m-m//i)*inv[m%i]%m]
fac=[1]
for i in r(2*m):fac+=[-~i*fac[i]%m]
q=int(input())
while q:q-=1;x,d,n=map(int,input().split());k=(x*inv[d])%m;print((pow(d,n,m)*fac[k+n-1]*inv[fac[k-1]%m])%m if d else pow(x,n,m))

Submission status: Runtime Error

Solution code:
m=1000003
r=range
inv=[0]+[pow(i,-1,m)for i in r(1,m)]
fac=[1]
for i in r(2*m):fac+=[-~i*fac[i]%m]
q=int(input())
while q:q-=1;x,d,n=map(int,input().split());k=(x*inv[d])%m;print((pow(d,n,m)*fac[k+n-1]*inv[fac[k-1]%m])%m if d else pow(x,n,m))

Submission status: Runtime Error

Solution code:
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.lang.reflect.Field;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;


public class Main {
    public static void main(String[] args) throws Exception {
        Field f = System.out.getClass().getDeclaredField("autoFlush");
        f.setAccessible(true);
        f.set(System.out, false);
        execute(System.in, System.out);
    }

    public static void execute(InputStream in, OutputStream out) {
        ExtendedScanner s = new ExtendedScanner(in);
        Out o = new Out(out);
        solve(s, o);
        o.flush();
        o.close();
    }

    public static void solve(ExtendedScanner sc, Out out) {
        int p = 1000003;
        int[] inv = invs(p);
        int[] fac = new int[2 * p + 1];
        fac[0] = 1;
        for (int i = 1; i <= 2 * p; i++) fac[i] = (int) (((long) fac[i - 1] * i) % p);
        int q = sc.nextInt();
        while (q --> 0) {
            long x = sc.nextInt();
            int d = sc.nextInt();
            int n = sc.nextInt();
            if (d == 0) {
                out.writeln(pow(x, n, p));
                continue;
            }
            int k = (int) ((x * inv[d]) % p);
            if ((k - 1) / p != (k + n - 1) / p) {
                out.writeln(0);
                continue;
            }
            long pow = pow(d, n, p);
            long v = ((long) fac[k + n - 1] * inv[fac[k - 1]]) % p;
            out.writeln((pow * v) % p);
        }
    }

    public static int[] invs(int p) {
        int[] inv = new int[p];
        inv[1] = 1;
        for (int i = 2; i < p; i++) {
            long q = p - p / i;
            long r = inv[p % i];
            inv[i] = (int) ((q * r) % p);
        }
        return inv;
    }

    public static long pow(long a, long b, int p) {
        if (b == 0 || a == 1) return 1;
        long res = 1;
        for (long pow = a, c = 1; b > 0;) {
            long lsb = b & -b;
            for (; lsb != c; c <<= 1, pow = (pow * pow) % p);
            res = (res * pow) % p;
            b ^= lsb;
        }
        return res;
    }
}


/**
 * @author https://atcoder.jp/users/suisen
 */
class BasicScanner {
    private final InputStream in;
    private final byte[] buf = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public BasicScanner(InputStream in) {this.in = in;}
    private boolean hasNextByte() {
        if (ptr < buflen) return true;
        ptr = 0;
        try {buflen = in.read(buf);}
        catch (final IOException e) {e.printStackTrace();}
        return buflen > 0;
    }
    private int readByte() {return hasNextByte() ? buf[ptr++] : -1;}
    public boolean hasNext() {
        while (hasNextByte() && !(33 <= buf[ptr] && buf[ptr] <= 126)) ptr++;
        return hasNextByte();
    }
    private StringBuilder nextSequence() {
        if (!hasNext()) throw new NoSuchElementException();
        final StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (33 <= b && b <= 126) {sb.appendCodePoint(b); b = readByte();}
        return sb;
    }
    public char nextChar() {
        return (char) readByte();
    }
    public String next() {
        return nextSequence().toString();
    }
    public String next(int len) {
        return new String(nextChars(len));
    }
    public char[] nextChars() {
        final StringBuilder sb = nextSequence();
        int l = sb.length();
        char[] dst = new char[l];
        sb.getChars(0, l, dst, 0);
        return dst;
    }
    public char[] nextChars(int len) {
        if (!hasNext()) throw new NoSuchElementException();
        char[] s = new char[len];
        int i = 0;
        int b = readByte();
        while (33 <= b && b <= 126 && i < len) {s[i++] = (char) b; b = readByte();}
        if (i != len) throw new NoSuchElementException(String.format("length %d is longer than the sequence.", len));
        return s;
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {minus = true; b = readByte();}
        if (b < '0' || '9' < b) throw new NumberFormatException();
        while (true) {
            if ('0' <= b && b <= '9') n = n * 10 + b - '0';
            else if (b == -1 || !(33 <= b && b <= 126)) return minus ? -n : n;
            else throw new NumberFormatException();
            b = readByte();
        }
    }
    public int nextInt() {return Math.toIntExact(nextLong());}
    public double nextDouble() {return Double.parseDouble(next());}
}


/**
 * @author https://atcoder.jp/users/suisen
 */
class Out {
    private final OutputStream out;
    private byte[] buf = new byte[1024];
    private int ptr = 0;
    private static final int AUTO_FLUSH_THRETHOLD = 1 << 17;

    public Out(OutputStream out) {
        this.out = out;
    }

    public void flush() {
        try {
            out.write(buf, 0, ptr);
            out.flush();
            ptr = 0;
        } catch (IOException e) {e.printStackTrace();}
    }

    public void close() {
        try {out.close();} catch (IOException e) {e.printStackTrace();}
    }

    public Out writeln() {return write('\n');}
    public Out writeln(Object o) {return write(o).write('\n');}
    public Out writeln(String s) {return write(s).write('\n');}
    public Out writeln(char[] c) {return write(c).write('\n');}
    public Out writeln(char   c) {return write(c).write('\n');}
    public Out writeln(byte   b) {return write(b).write('\n');}
    public Out writeln(int    x) {return write(x).write('\n');}
    public Out writeln(long   x) {return write(x).write('\n');}
    public Out writeln(double d) {return write(d).write('\n');}

    public Out writeSpace() {return write(' ');}
    
    public Out write(Object o) {
        return write(o.toString());
    }

    public Out write(String s) {
        try {
            Field strValueField = s.getClass().getDeclaredField("value");
            strValueField.setAccessible(true);
            byte[] b = (byte[]) strValueField.get(s);
            int l = s.length();
            if (l > AUTO_FLUSH_THRETHOLD) {
                flush();
                int i = 0;
                while (i + AUTO_FLUSH_THRETHOLD < l) {
                    out.write(b, i, AUTO_FLUSH_THRETHOLD);
                    out.flush();
                    i += AUTO_FLUSH_THRETHOLD;
                }
                ensureCapacity(l - i);
                System.arraycopy(b, i, buf, 0, l - i);
                ptr = l - i;
            } else {
                ensureCapacity(ptr + l);
                System.arraycopy(b, 0, buf, ptr, l);
                ptr += l;
            }
        } catch (Exception e) {e.printStackTrace();}
        return this;
    }

    public Out write(char[] c) {
        int l = c.length;
        if (l > AUTO_FLUSH_THRETHOLD) {
            flush();
            ensureCapacity(AUTO_FLUSH_THRETHOLD);
            int i = 0;
            while (i + AUTO_FLUSH_THRETHOLD < l) {
                for (int j = 0; j < AUTO_FLUSH_THRETHOLD; j++) {
                    buf[ptr++] = (byte) c[i + j];
                }
                flush();
                i += AUTO_FLUSH_THRETHOLD;
            }
            for (; i < l; i++) {
                buf[ptr++] = (byte) c[i];
            }
        } else {
            ensureCapacity(ptr + l);
            for (char ch : c) buf[ptr++] = (byte) ch;
        }
        return this;
    }

    public Out write(char c) {
        ensureCapacity(ptr + 1);
        buf[ptr++] = (byte) c;
        return this;
    }

    public Out write(byte b) {
        ensureCapacity(ptr + 1);
        buf[ptr++] = b;
        return this;
    }

    public Out write(int x) {
        if (x == 0) {
            ensureCapacity(ptr + 1);
            buf[ptr++] = '0';
            return this;
        }
        int d = stringSize(x);
        ensureCapacity(ptr + d);
        if (x < 0) {
            buf[ptr++] = '-';
            x = -x;
            d--;
        }
        int j = ptr + d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        ptr += d;
        return this;
    }

    public Out write(long x) {
        if (x == 0) {
            ensureCapacity(ptr + 1);
            buf[ptr++] = '0';
            return this;
        }
        int d = stringSize(x);
        ensureCapacity(ptr + d);
        if (x < 0) {
            buf[ptr++] = '-';
            x = -x;
            d--;
        }
        int j = ptr + d; 
        while (x > 0) {
            buf[--j] = (byte) ('0' + (x % 10));
            x /= 10;
        }
        ptr += d;
        return this;
    }

    public Out write(double d) {
        return write(Double.toString(d));
    }

    private void ensureCapacity(int cap) {
        if (cap > AUTO_FLUSH_THRETHOLD) {
            flush();
        }
        if (cap >= buf.length) {
            int newLength = buf.length;
            while (newLength < cap) newLength <<= 1;
            byte[] newBuf = new byte[newLength];
            System.arraycopy(buf, 0, newBuf, 0, buf.length);
            buf = newBuf;
        }
    }
    private static int stringSize(long x) {
        int d = 1;
        if (x >= 0) {d = 0; x = -x;}
        long p = -10;
        for (int i = 1; i < 19; i++, p *= 10) if (x > p) return i + d;
        return 19 + d;
    }
    private static int stringSize(int x) {
        int d = 1;
        if (x >= 0) {d = 0; x = -x;}
        int p = -10;
        for (int i = 1; i < 10; i++, p *= 10) if (x > p) return i + d;
        return 10 + d;
    }
}


/**
 * @author https://atcoder.jp/users/suisen
 */
final class ExtendedScanner extends BasicScanner {
    public ExtendedScanner(InputStream in) {super(in);}
    public int[] ints(final int n) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> nextInt());
        return a;
    }
    public int[] ints(final int n, final IntUnaryOperator f) {
        final int[] a = new int[n];
        Arrays.setAll(a, $ -> f.applyAsInt(nextInt()));
        return a;
    }
    public int[][] ints(final int n, final int m) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m));
        return a;
    }
    public int[][] ints(final int n, final int m, final IntUnaryOperator f) {
        final int[][] a = new int[n][];
        Arrays.setAll(a, $ -> ints(m, f));
        return a;
    }
    public long[] longs(final int n) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> nextLong());
        return a;
    }
    public long[] longs(final int n, final LongUnaryOperator f) {
        final long[] a = new long[n];
        Arrays.setAll(a, $ -> f.applyAsLong(nextLong()));
        return a;
    }
    public long[][] longs(final int n, final int m) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m));
        return a;
    }
    public long[][] longs(final int n, final int m, final LongUnaryOperator f) {
        final long[][] a = new long[n][];
        Arrays.setAll(a, $ -> longs(m, f));
        return a;
    }
    public char[][] charArrays(final int n) {
        final char[][] c = new char[n][];
        Arrays.setAll(c, $ -> nextChars());
        return c;
    }
    public char[][] charArrays(final int n, final int m) {
        final char[][] c = new char[n][];
        Arrays.setAll(c, $ -> nextChars(m));
        return c;
    }
    public double[] doubles(final int n) {
        final double[] a = new double[n];
        Arrays.setAll(a, $ -> nextDouble());
        return a;
    }
    public double[][] doubles(final int n, final int m) {
        final double[][] a = new double[n][];
        Arrays.setAll(a, $ -> doubles(m));
        return a;
    }
    public String[] strings(final int n) {
        final String[] s = new String[n];
        Arrays.setAll(s, $ -> next());
        return s;
    }
    public String[] strings(final int n, final int m) {
        final String[] s = new String[n];
        Arrays.setAll(s, $ -> next(m));
        return s;
    }
}

Submission status: Runtime Error

Solution code:
# E - Product of Arithmetic Progression

import sys
input = sys.stdin.buffer.readline

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

# a//b (MOD p)
def div_mod(a, b, p = MOD):
    return (a * pow(b, p-2, p)) % p

factorial_memo = [1, 1]
for i in range(2, 10**5 + MOD):
    factorial_memo.append((factorial_memo[-1] * i) % MOD)

for _ in range(Q):
    x, d, n = map(int, input().split())
    if x == 0 and d == 0:
        print(0)
    elif x == 0:
        ans = factorial_memo[n-1]
        ans *= pow(d, n-1, MOD)
        ans %= MOD
        print(ans)
    elif d == 0:
        print(factorial_memo[x])
    else:
        ans = pow(d, n, MOD)
        x_divided_by_d = div_mod(x, d, MOD)
        ans *= factorial_memo[x_divided_by_d + (n-1)]
        ans %= MOD
        ans = div_mod(ans, factorial_memo[x_divided_by_d - 1], MOD)
        print(ans)

Submission status: Runtime Error

Solution code:
Q = int(input())
mod = int(1e+6 + 3)
def gcd(a, b):
  p, q = a, b
  while q != 0:
    a, b = b, a % b
  return a
def doublestep(a):
  li = []
  while a != 0:
    li = [a%2] + li[:]
    a //= 2
  return li
def doubling(z, num):
  y = doublestep(num)
  tet = 1
  for i in range(len(y)):
    if y[i] == 1:
      tet *= z
      tet %= mod
    if i != len(y) - 1:
      tet *= tet
      tet %= mod
  return tet
modi = doublestep(mod-2)
def inved(s):
  y = 1
  for i in range(len(modi)):
    if modi[i] == 1:
      y *= s
      y %= mod
    if i != len(modi) - 1:
      y *= y
      y %= mod
  return y

frac = [1]
for i in range(2 * mod):
  frac.append((frac[i]*(i+1))%mod)
for i in range(Q):
  x, d, n = map(int, input().split())
  if x == 0:
    print(0)
  else:
    if d == 0:
      print(doubling(x, n))
    else:
      if n >= mod:
        print(0)
      else:
        dn = doubling(d, n)
        xinvd = x * inved(d, mod - 2) - 1
        xinvd %= mod
        print((dn * frac[xinvd + n] * inved(frac[xinvd])) % mod)