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: Wrong Answer

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,b=(x-1)*D%mod,(x+(n-1)%mod*d)*D%mod
    #print(a,b)
    if a<b:
        if 1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        #else:
        #    value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=x*D%mod,(x+(n-1)%mod*d)*D%mod
    #print(a,b)
    if 1<=a<=b:
        if 1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        #else:
        #    value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=x*D%mod,(x+(n-1)%mod*d)*D%mod
    if a<=b:
        if a>1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        else:
            value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a<=b and b<mod:
        if 1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        else:
            value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a<=b and b<mod:
        if a>1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        else:
            value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a>=0 and a<b and b<mod:
        if a>1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        else:
            value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=(x-d)*D%mod,(x+(n-1)*d)*D%mod
    if a>=0 and a<b and b<mod:
        if a>1:
            value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        else:
            value=fac[b]*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)

Submission status: Wrong Answer

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,b=(x-d)*D%mod,(x+(n-1)*d)*D%mod
    value=fac[b]*pow(fac[a],mod-2,mod)*pow(d,n,mod)
    print(value%mod)

Submission status: Wrong Answer

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
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:
        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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 解説思い出し AC
import sys
def main():
    mod = 10**6+3
    cum_prod = [0]
    p = 1
    for i in range(1, 2*mod):
        p = p * i % mod
        cum_prod.append(p)
    Q = int(input())
    Ans = []
    for x, d, n in zip(*[iter(map(int, sys.stdin.read().split()))]*3):
        if n>=mod or x==0:
            Ans.append(0)
        elif d==0:
            Ans.append(pow(x, n, mod))
        else:
            x_d = x * pow(d, mod-2, mod) % mod
            Ans.append(pow(d, n, mod) * cum_prod[x_d + n-1] % mod * pow(cum_prod[x_d-1], mod-2, mod) % mod)
    print("\n".join(map(str, Ans)))

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod=10**6+3
n_max=mod
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
  FI[i+1]=pow(F[i+1],mod-2,mod)
for i in range(int(input())):
  x,d,n=map(int,input().split())
  if d==0:
    print(pow(x,n,mod))
  else:
    print(((pow(d,n,mod))*F[(x*pow(d,mod-2,mod)+n-1)%mod]*FI[(x*pow(d,mod-2,mod)-1)%mod])%mod)

Submission status: Wrong Answer

Solution code:
MOD = 1000003
facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, MOD):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def task(x, d, n, MOD=MOD):
    if x == 0:
        return 0
    if d == 0:
        return pow(x, n, MOD)
    
    xdivd = (x*invs[d]) % MOD
    if xdivd - 1 <= MOD and MOD <= xdivd + n -1:
        return 0
    ans = (facts[xdivd + n -1]*invfacts[xdivd - 1]) % MOD
    ans = (ans*pow(d, n, MOD)) % MOD
    return ans

Q = int(input())
for _ in range(Q):
    x, d, n = map(int, input().split())
    ret = task(x, d, n)
    print(ret+1)

Submission status: Wrong Answer

Solution code:
Q = int(input())
div = 1000003
div_2 = div/2
for _ in range(Q):
  x, d, n = map(int, input().split())
  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: Wrong Answer

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

# n, x =2, 100
# blu = [[85, 2, 3],[60, 1, 1]]

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: Wrong Answer

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

MOD = 10 ** 6 + 3

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

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

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

Submission status: Wrong Answer

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

MOD = 10 ** 6 + 3

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod=10**6+3

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod=10**6+3

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

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

Submission status: Wrong Answer

Solution code:
# 入力
Q = int(input())
x, d, n = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), (), ())
)

MOD = 1000003


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

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

    __repr__ = __str__

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

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

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

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

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

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

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

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

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

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


# MOD未満の整数について、階乗を求めておく
# 各クエリに対して、d^n * (x/d + (n - 1))! / ((x/d) - 1)! を回答する
f = [0 for _ in range(MOD)]
f[0] = ModInt(1)
for i in range(1, MOD):
    f[i] = i * f[i - 1]


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


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

# 出力
print(ans)

Submission status: Wrong Answer

Solution code:
# 入力
Q = int(input())
x, d, n = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), (), ())
)

MOD = 1000003


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

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

    __repr__ = __str__

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

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

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

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

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

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

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

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

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

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


# MOD未満の整数について、階乗を求めておく
# 各クエリに対して、d^n * (x/d + (n - 1))! / ((x/d) - 1)! を回答する
f = [0 for _ in range(MOD)]
g = [0 for _ in range(MOD)]
f[0] = ModInt(1)
g[0] = ModInt(1)
for i in range(1, MOD):
    f[i] = i * f[i - 1]
    g[i] = g[i - 1] / i


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


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

# 出力
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.readline

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

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

for _ in range(Q):
    x, d, n = inpl()
    n = n%MOD
    print((g1[n] * cmb((x*inverse[d] + n - 1)%MOD, n, MOD) * pow(d, n, MOD))%MOD)

Submission status: Wrong Answer

Solution code:
def inpl(): return list(map(int, input().split()))
Q = int(input())
 
MOD = 10**6 + 3
def cmb(n, r, mod):
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
size = MOD + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル

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

for _ in range(Q):
    x, d, n = inpl()
    n = n%MOD
    print((g1[n] * cmb((x*inverse[d] + n - 1)%MOD, n, MOD) * pow(d, n, MOD))%MOD)

Submission status: Wrong Answer

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

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

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

comb_build(MAX)

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

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

Submission status: Wrong Answer

Solution code:
mod=1000003
Q=int(input())
kaijo=[1]*mod
for i in range(1,mod):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*mod
gyaku[mod-1]=pow(kaijo[mod-1],mod-2,mod)
for i in range(mod-1,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
for q in range(Q):
    x,d,n=map(int,input().split())
    if d==0:
        print(pow(x,n,mod))
    s=x*pow(d,mod-2,mod)%mod
    if s+n-1>=mod:
        print(0)
    else:
        print(pow(d,n,mod)*kaijo[s+n-1]*gyaku[s-1]%mod)

Submission status: Wrong Answer

Solution code:
mod=1000003
Q=int(input())
kaijo=[1]*mod
for i in range(1,mod):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*mod
gyaku[mod-1]=pow(kaijo[mod-1],mod-2,mod)
for i in range(mod-1,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
for q in range(Q):
    x,d,n=map(int,input().split())
    if d==0:
        print(pow(x,n,mod))
    s=x*pow(d,mod-2,mod)%mod
    if s+n>=mod:
        print(0)
    else:
        print(pow(d,n,mod)*kaijo[s+n-1]*gyaku[s-1]%mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

# 階乗たくさん使う時用のテーブル準備
# MAX：階乗に使う数値の最大以上まで作る
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
    # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
    inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
    for i in range(MAX-2, 0, -1):
        # 最後から戻っていくこのループならMAX回powするより処理が速い
        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=(x*invd+n-1)%MOD

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

Submission status: Wrong Answer

Solution code:
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 n >= p or x == 0:
        print(0)
        continue
    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)

Submission status: Wrong Answer

Solution code:
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 n >= p or x == 0:
        print(0)
        continue
    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 + n - 1 >= p:
        print(0)
        continue

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

Submission status: Wrong Answer

Solution code:
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 n >= p or x == 0 or x + n - 1 >= p:
        print(0)
        continue
    if d == 0:
        print(pow(x, n, p))
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)

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

Submission status: Wrong Answer

Solution code:
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 n >= p or x == 0:
        print(0)
        continue
    if d == 0:
        print(pow(x, n, p))
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)

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

Submission status: Wrong Answer

Solution code:
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)
f[0] = 0
invf[0] = 0

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

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

Submission status: Wrong Answer

Solution code:
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 n >= p or d == 0 or x == 0:
        print(0)
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)

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

Submission status: Wrong Answer

Solution code:
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 n >= p or d == 0:
        print(0)
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)

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

Submission status: Wrong Answer

Solution code:
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 n >= p:
        print(0)
        continue
    
    inv_d = pow(d, p - 2, p)
    d_n = pow(d, n, p)

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

Submission status: Wrong Answer

Solution code:
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(d,n)
    check=((p-d)*inv(x))%p
    if 0<=check<=n-1:
        return 0
    a=(x*inv(d))%p
    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))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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