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:
p=1000003
inv=[0,1]
for i in range(2,p):inv+=[(p-p//i)*inv[p%i]%p]
fac=[1]
for i in range(2*p):fac+=[-~i*fac[i]%p]
q=int(input())
for i in range(q):
 x,d,n=map(int,input().split())
 k=(x*inv[d])%p
 if d==0:print(pow(x,n,p))
 elif n>=((p-x)*inv[d])%p:print(0)
 else:print((pow(d,n,p)*fac[k+n-1]*inv[fac[k-1]%p])%p)

Submission status: Wrong Answer

Solution code:
mod=1000003
fact=[1]
revfact=[1]
for i in range(1,3*mod):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[i],mod-2,mod))
q=int(input())
for _ in range(q):
  x,d,n=map(int,input().split())
  if n>=mod:
    print(0)
    continue
  if d==0:
    print(pow(x,n,mod))
    continue
  if x==0:
    print(0)
    continue
  x*=pow(d,mod-2,mod)
  x%=mod
  ans=fact[x+n-1]*revfact[x-1]*pow(d,n,mod)
  ans%=mod
  print(ans)

Submission status: Wrong Answer

Solution code:
mod=1000003
fact=[1]
revfact=[1]
for i in range(1,2*mod+10):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[i],mod-2,mod))
q=int(input())
for _ in range(q):
  x,d,n=map(int,input().split())
  if n>=mod:
    print(0)
    continue
  if d==0:
    print(pow(x,n,mod))
    continue
  if x==0:
    print(0)
    continue
  x*=pow(d,mod-2,mod)
  x%=mod
  ans=fact[x+n-1]*revfact[x-1]*pow(d,n,mod)
  ans%=mod
  print(ans)

Submission status: Wrong Answer

Solution code:
mod=1000003
fact=[1]
revfact=[1]
for i in range(1,mod):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[i],mod-2,mod))
q=int(input())
for _ in range(q):
  x,d,n=map(int,input().split())
  if n>=mod:
    print(0)
    continue
  if d==0:
    print(pow(x,n,mod))
    continue
  if x==0:
    print(0)
    continue
  x*=pow(d,mod-2,mod)
  x%=mod
  ans=fact[(x+n-1)%mod]*revfact[(x-1)%mod]*pow(d,n,mod)
  ans%=mod
  print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j] = pow(self.power[j],self.mod-2,self.mod)

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(2*10**6, mod)


def rev(X):
    return pow(X, mod-2, mod)


def count_div(L, R, D):
    return not bool(R//D - (L-1)//D)


def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if count_div(y, y+n-1, mod):
            y = y % mod
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y)*y
            print(ans % mod)
            return
        else:
            ans = 0
            print(ans % mod)
            return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(mod-1, mod)


def rev(X):
    return pow(X, mod-2, mod)


def count_div(L, R, D):
    return not bool(R//D - (L-1)//D)


def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if count_div(y, y+n-1, mod):
            y = y % mod
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y)*y
            print(ans % mod)
            return
        else:
            ans = 0
            print(ans % mod)
            return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(mod-1, mod)


def rev(X):
    return pow(X, mod-2, mod)


def count_div(L, R, D):
    return not bool(R//D - (L-1)//D)


def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if count_div(y, y+n-1, mod):
            y = y % mod
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y-1)
            print(ans % mod)
            return
        else:
            ans = 0
            print(ans % mod)
            return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(mod-1, mod)


def rev(X):
    return pow(X, mod-2, mod)


def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if (y+n-1) % mod != 0 and (y) % mod != 0 and (y+n-1)//mod == (y-1)//mod:
            y = y % mod
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y-1)
            print(ans % mod)
            return
        else:
            ans = 0
            print(ans % mod)
            return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(mod-1, mod)


def rev(X):
    return pow(X, mod-2, mod)

def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if (y+n-1)%mod!=0 and (y-1)%mod!=0 and (y+n-1)//mod == (y-1)//mod:
            y = y % mod          
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y-1)
            print(ans%mod)
            return
        else:
            ans = 0
            print(ans%mod)
            return



def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod=1000003
g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,mod):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)
def f(l,r):
  if (l//mod)!=(r//mod):
    return 0
  return g1[r%mod]*g2[(l-1)%mod]%mod
Q=int(input())
X,D,N=0,0,0
for i in range(Q):
  X,D,N=map(int,input().split())
  if D==0:
    print(pow(X,N,mod))
  else:
    print(pow(D,N,mod)*f(X*inv[D]%mod,(X*inv[D]+N-1)%mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

q = int(readline())
xdn = list(map(int,read().split()))
mod = 1_000_003

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = mod + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(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

comInit(max)

def prod(l,r):
    #lからr-1までの累積
    res = (fac[r-1] * finv[l-1])%mod
    return res

def solve(x,d,n):
    x0 = (x * inv[d])%mod
    xn = x0 + n
    if(xn > mod)|(x0==0):
        return 0
    res = (prod(x0,xn) * pow(d,n,mod))%mod
    return res


ans = []
for i in range(q):
    x,d,n = xdn[i*3:i*3+3]
    ans.append(solve(x,d,n))

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

Submission status: Wrong Answer

Solution code:
def main():
    q = int(input())
    mod = 1000003
    fact = [1, 1]
    for i in range(2, mod+1):
        fact.append(fact[-1]*i % mod)

    for i in range(q):
        x, d, n = map(int, input().split())
        if d == 0:
            print(pow(d, n, mod))
            continue
        elif n >= mod:
            print(0)
            continue
        b = -x*pow(d, mod-2, mod) % mod
        if b >= n:
            print(pow(fact[b-n], mod-2, mod)*fact[b]*pow(-d, n, mod) % mod)
        else:
            print(0)


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

mod = 10 ** 6 + 3
U = 10 ** 6 + 2

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


def GCD(x, y):
    if y == 0:
        return x
    return GCD(y, x % y)


def msol(x, d, n):
    if d == 1:
        if x + n - 1 >= mod:
            return 0
        res = fact[x+n-1]*pow(fact[x-1], mod-2, mod) % mod
        return res

    inv = pow(d, mod-2, mod)
    y = x * inv % mod
    C = pow(d, n, mod)
    if y + n - 1 >= mod or y == 0:
        return 0
    res = fact[y+n-1]*pow(fact[y-1], mod-2, mod) % mod
    res = res * C % mod
    return res


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

mod = 10 ** 6 + 3
U = 10 ** 6 + 2

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


def GCD(x, y):
    if y == 0:
        return x
    return GCD(y, x % y)


def msol(x, d, n):
    if d == 1:
        if x + n - 1 >= mod:
            return 0
        res = fact[x+n-1]*pow(fact[x-1], mod-2, mod) % mod
        return res

    inv = pow(d, mod-2, mod)
    y = x * inv % mod
    C = pow(d, n, mod)
    if y + n - 1 >= mod:
        return 0
    res = fact[y+n-1]*pow(fact[y-1], mod-2, mod) % mod
    res = res * C % mod
    return res


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
Q = int(input())
mod = 10 ** 6 + 3
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(mod - 1, mod)

for _ in range(Q):
  x, d, n = map(int, input().split())
  z = -x * pow(d, mod - 2, mod) % mod
  v = -z % mod
  if z < n:
    print(0)
    continue
  #print(z, v)
  res = f.factorial(v + n - 1) * pow(d, v + n - 1, mod) % mod
  #print(res, f.ifactorial(v - 1), pow(f.factorial(v - 1), mod - 2, mod), pow(d, v - 1, mod))
  res *= f.ifactorial(v - 1) * pow(pow(d, v - 1, mod), mod - 2, mod) % mod
  res %= mod
  print(res)

Submission status: Wrong Answer

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

inv=[pow(frac[i],mod-2,mod) for i in range(len(frac))]

for _ in range(int(input())):
    x,d,n=map(int,input().split())
    if n>=mod:
        print(0)
    elif d==0:
        print(pow(x,n,mod))
    else:
        c=(x*pow(d,mod-2,mod))%mod
        if c==0 or c+n-1>=mod:
            print(0)
        else:
            ans=frac[c+n-1]*inv[c-1]*pow(d,n,mod)
            ans%=mod
            print(ans)

Submission status: Wrong Answer

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

inv=[pow(frac[i],mod-2,mod) for i in range(len(frac))]

for _ in range(int(input())):
    x,d,n=map(int,input().split())
    if n>=mod:
        print(0)
    else:
        c=(x*pow(d,mod-2,mod))%mod
        if c==0 or c+n-1>=mod:
            print(0)
        else:
            ans=frac[c+n-1]*inv[c-1]*pow(d,n,mod)
            ans%=mod
            print(ans)

Submission status: Wrong Answer

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

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

T = [1]
for n in range(1, mod+1):
    T.append(T[-1]*n%mod)

for x, d, n in Query:
    start = x*pow(d, mod-2, mod)%mod
    if start == 0 or start + n-1 >= mod:
        ans = 0
    else:
        ans = pow(d, n, mod) * pow(T[start-1], mod-2, mod) * T[start+n-1] % mod
    print(ans)

Submission status: Wrong Answer

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

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

T = [1]
for n in range(1, mod+1):
    T.append(T[-1]*n%mod)

for x, d, n in Query:
    start = x*pow(d, mod-2, mod)%mod
    if start == 0 or start + n-1 >= mod:
        ans = -1
    else:
        ans = pow(d, n, mod) * pow(T[start-1], mod-2, mod) * T[start+n-1] % mod
    print(ans)

Submission status: Wrong Answer

Solution code:

"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

    if d == 0 and x == 0:
        print (pow(x,n,mod))
        continue
    elif x == 0:
        ans = fac[(n-1) % mod]
        ans *= pow(d,n-1,mod)
        print (ans % mod)
        continue
    elif d == 0:
        print (pow(x,n,mod))
    elif n == 1:
        print (x)
        continue

    fi = x * inverse(d,mod) % mod
    
    if fi + n >= mod or fi % mod == 0:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    if fi >= 2:
        print (pow(d,n,mod) * fac[(fi+n-1) % mod] * inv[(fi-1) % mod] % mod)
    else:
        print (pow(d,n,mod) * fac[(fi+n-1) % mod]  % mod)

Submission status: Wrong Answer

Solution code:

"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

    if d == 0:
        print (pow(x,n,mod))
        continue
    elif x == 0:
        print (0)
        continue
    elif n == 1:
        print (x)
        continue

    fi = x * inverse(d,mod) % mod
    
    if fi + n >= mod or fi % mod == 0:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    if fi >= 2:
        print (pow(d,n,mod) * fac[(fi+n-1) % mod] * inv[(fi-1) % mod] % mod)
    else:
        print (pow(d,n,mod) * fac[(fi+n-1) % mod]  % mod)

Submission status: Wrong Answer

Solution code:

"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

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

    fi = x * inverse(d,mod) % mod
    #print (fi)
    if fi + n >= mod or fi % mod == 0:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    print (pow(d,n,mod) * fac[(fi+n-1) % mod] * inv[(fi-1) % mod] % mod)

Submission status: Wrong Answer

Solution code:

"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

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

    fi = x * inverse(d,mod) % mod
    #print (fi)
    if fi + n >= mod:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    print (pow(d,n,mod) * fac[(fi+n-1) % mod] * inv[(fi-1) % mod] % mod)

Submission status: Wrong Answer

Solution code:

"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

    fi = x * inverse(d,mod) % mod
    #print (fi)
    if fi + n >= mod:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    print (pow(d,n,mod) * fac[(fi+n-1) % mod] * inv[(fi-1) % mod] % mod)

Submission status: Wrong Answer

Solution code:

"""
可能性:
数学的にO(1)→濃厚
前準備して瞬殺→全部違うからありえなさそう

展開式から計算？→結局n項になっちゃう…

1つ項が進むと、mod1000003はd個右にずれる(右端でループ)
→0に来ることがあれば必ず0

d,n固定の時、x1の結果からx2の結果を導出できればlogNで解ける
→そんなシンプルにはいかなそう…

========解答を見た=========
？？？？？？
分かるけど…どういうこと…

→簡単に解ける問題に落とし込むのか…
→制約が簡単verを色々考慮し、落とし込めないか考えるべきだった

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

mod = 10 ** 6 + 3
fac,inv = modfac(mod-1, mod)

#print (len(inv))
Q = int(input())

for i in range(Q):

    x,d,n = map(int,input().split())

    fi = x * inverse(d,mod) % mod
    #print (fi)
    if fi + n >= mod:
        print (0)
        continue

    #print (pow(d,n,mod) , fac[fi+n-1] , inv[fi-1] , mod)
    print (pow(d,n,mod) * fac[fi+n-1] * inv[fi-1] % mod)

Submission status: Wrong Answer

Solution code:
Q = int(input())
mod = int(1e+6 + 3)

def doubling(n, m):
  y = 1
  p = n
  while m != 0:
    if m % 2 == 1:
      y *= p
      y %= mod
    m //= 2
    p *= n
    p %= mod
  return y

def inved(s):
  x, y, u, v, k, l = 1, 0, 0, 1, s, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

frac = [1]
for i in range(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:
        xinvd = x * inved(d) - 1
        xinvd %= mod
        if xinvd + n >= mod:
          print(0)
        else:
          dn = doubling(d, n)
          print((dn * frac[xinvd + n] * inved(frac[xinvd])) % mod)

Submission status: Wrong Answer

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+3):
    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)
    try:
        tmp*=fct[x+n-1]
    except:
        print(0)
        continue
    if x>=2:
        tmp*=pow(fct[x-1],mod-2,mod)
    tmp%=mod
    print(tmp)

Submission status: Wrong Answer

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)
    try:
        tmp*=fct[x+n-1]
    except:
        print(0)
        continue
    if x>=2:
        tmp*=pow(fct[x-1],mod-2,mod)
    tmp%=mod
    print(tmp)

Submission status: Wrong Answer

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)
    try:
        tmp*=fct[x+n-1]
    except:
        print(0)
        continue
    if x>=1:
        tmp*=pow(fct[x-1],mod-2,mod)
    tmp%=mod
    print(tmp)

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