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

Submission status: Wrong Answer

Solution code:
class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]

    def comb(self, n, r):
        """
        :return: nCr
        """
        return self.f[n] * self.inv[n - r] * self.inv[r] % self.mod

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)%g, (s-1)%g
        if y != 0 and s + 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)%g, (s-1)%g
        if s + 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)

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)%g, (s-1)%g
        if y != 0 and y + n < 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)

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)%g, (s-1)%g
        if x != 0 and x + n < 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)

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)%g, (s-1)%g
        if x!=0 and y!=0 and x >= y :
            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)

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)%g, (s-1)%g
        if x >= y > 0:
            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)

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)%g, (s-1)%g
        if x >= y:
            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)

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)
        print(div(fr[(s+n-1)%g], fr[(s-1)%g]) * pow(d, n, g) % g)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    Q = II()
    query = []
    for _ in range(Q):
        query.append(LI())
    fact = [1] * MOD
    for i in range(1, MOD):
        fact[i] = fact[i - 1] * i % MOD
    ifact = [1] * MOD
    ifact[MOD - 1] = pow(fact[MOD - 1], MOD - 2, MOD)
    for i in range(MOD - 1, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    for x, d, n in query:
        if d == 0:
            ans = pow(x, n, MOD)
        else:
            x = x * pow(d, MOD - 2, MOD) % MOD
            if (x + n - 1) // MOD > (x - 1) // MOD:
                ans = 0
            factor = pow(d, n, MOD)
            start, end = (x - 1) % MOD, (x + n - 1) % MOD
            perm = fact[end] * ifact[start] % MOD
            ans = perm * factor % MOD
        print(ans)
    return

main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    Q = II()
    query = []
    for _ in range(Q):
        query.append(LI())
    fact = [1] * MOD
    for i in range(1, MOD):
        fact[i] = fact[i - 1] * i % MOD
    ifact = [1] * MOD
    ifact[MOD - 1] = pow(fact[MOD - 1], MOD - 2, MOD)
    for i in range(MOD - 1, 0, -1):
        ifact[i - 1] = ifact[i] * i % MOD
    for x, d, n in query:
        if d == 0:
            ans = pow(x, n, MOD)
        else:
            x = x * pow(d, MOD - 2, MOD) % MOD
            if (x + n - 1) // MOD > (x - 1) // MOD:
                ans = 0
            factor = pow(d, n, MOD)
            start, end = x % MOD, (x + n - 1) % MOD
            perm = fact[end] * ifact[start - 1] % MOD
            ans = perm * factor % MOD
        print(ans)
    return

main()

Submission status: Wrong Answer

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

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

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

for i in range(Q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, MOD))
    if d == 1:
        if x + (n - 1) * d >= MOD:
            print(0)
        else:
            print(fact[x + (n - 1)] * rfact[x - 1] % MOD)
    else:
        rd = pow(d, MOD - 2, MOD)
        rx = (rd * x) % MOD
        if rx == 0:
            print(0)
        elif rx + n - 1 >= MOD:
            print(0)
        else:
            print((fact[rx + n - 1] * pow(fact[rx - 1], MOD - 2, MOD) * pow(d, n, MOD)) % MOD)

Submission status: Wrong Answer

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

Solution code:
m=1000003
def inv(i):
    return pow(i,m-2,m)
def sol(_inp=input):
    n=int(_inp())
    fact=[1 for _ in range(m)]
    for i in range(m-1):
        fact[i+1]=fact[i]*(i+1)%m
    results=[1 for _ in range(n)]
    for i in range(n):
        x,d,n=map(int,_inp().split())
        if d==0:
            for _ in range(n):
                results[i]=(x**n)%m
        else:
            d_inv=inv(d)
            if (x*d_inv+n-1)//m>(x*d_inv-1)//m:
                results[i]=0
            else:
                results[i]=fact[(x*d_inv+n-1)%m]*inv(fact[(x*d_inv-1)%m])%m
                for _ in range(n):
                    results[i]=results[i]*d%m
    return '\n'.join(str(r) for r in results)

Submission status: Wrong Answer

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

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))
    if p == 0:
        print(0)
        continue
    if 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: Wrong Answer

Solution code:
q = int(input())

anss = []
for i in range(q):
    x, d, n = map(int,input().split())
    ans = 1
    for i in range(n):
        ans *= (x+i*d)
    anss.append(ans)

for i in range(q):
    print(anss[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
w = 1000003
for i in range(N):
  x,d,n = list(map(int,input().split()))
  M = x
  for j in range(1,n):
    M = M * (x + (j - 1))
  print(M%w)

Submission status: Wrong Answer

Solution code:
Q = int(input())
answer_list = list()

for _ in range(Q):
    x, d, n = list(map(int, input().split()))
    answer_list.append((n * x + (n - 1) / 2 * d) % 1000003)
    
for answer in answer_list:
    print(answer)

Submission status: Wrong Answer

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 p == 0:
        print(0)
        continue
    if 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: Wrong Answer

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 p == 0:
        print(0)
        continue
    if p + n - 1 >= mod:
        print(0)
        continue
    print(frac[(p+n-1)%mod]*pow(frac[p-1], mod-2, mod)*pow(d, n, mod)%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
X = np.zeros((Q,3))
for i in range(Q):
  X[i] = list(map(int,input().split()))
X = X.T
num = int(np.max(X[2]))-1
output = np.zeros((1,Q))
output[0] = X[0]
for i in range (num):
  X[0] += X[1] #x += d
  mask = np.where(i+1<X[2],1,1/X[0])
  X[0] *= mask
  output[0] *= X[0]
  output %= 1000003
for i in range(len(output)):
  print(output[i])

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
Q = int(input())
sub = 1000000007
for _ in range(Q):
    p = 1
    x, d, n = map(int, input().split())
    for i in range(1, n + 1):
        p = p%sub
        m = x + (d * ((i - 1)%sub))
        m = m%sub
        p *= m
    ans = p%sub
    print(ans)

Submission status: Wrong Answer

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
    print(frac[(p+n-1)%mod]*pow(frac[p-1], mod-2, mod)*pow(d, n, mod)%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

Submission status: Wrong Answer

Solution code:
P = 1000003

def func(x,d,n):
    if n==1:
        return x
    elif n%2==1:
        return (x * func(x+d, d, (n-1) // 2 ) * func(x+d + (n-1)//2*d , d, (n-1)//2 )) % P
    else :
        return  (func(x, d, (n) // 2 ) * func(x+ (n)//2*d , d, n//2 ) ) % P

def func2(x,d,n):
    ret=1
    y=x-d
    for i in range(n):
        y+=d
        ret=(ret+d)%P
        if not ret:
            return ret
    return ret
Q=int(input())
for i in range(Q):
    x,d,n=[int(x) for x in input().split()]
    if n >= P:
        print (0)
    else:
        print(func2(x,d,n))

Submission status: Wrong Answer

Solution code:
N = int(input())

for _ in range(N):
  x,d,n = map(int,input().split())
  
  ans = x
  for i in range(1,n):
    ans *= x + i*d
  print(ans)

Submission status: Wrong Answer

Solution code:
q = int(input())
for i in range(q):
    x, d, n = map(int, input().split())
    print(0)

Submission status: Wrong Answer

Solution code:
n=int(input())
for j in range(n):
    import numpy
    a=list(map(int,input().split(" ")))
    b=[]
    for i in range(a[2]):
        b.append(a[0]+((i-1)*(a[1])))
    result=numpy.prod(b)
    print(result%1000003)

Submission status: Wrong Answer

Solution code:
q = int(input())
line = [list(map(int, input().split())) for _ in range(q)]

import numpy as np

for x,d,n in line:
  pro = np.array([x + i*d for i in range(n)])
  answer = np.prod(pro)
  print(np.mod(answer,1000003))

Submission status: Wrong Answer

Solution code:
q = int(input())
print(q)
params = [[int(v) for v in input().split()] for i in range(q)]
print(params)

M = 1000003
for param in params:
  x, d, n = param
  s = 1
  for i in range(n):
    s *= ( (x + i * d) % M )
    
  r = s % M
  print(r)

Submission status: Wrong Answer

Solution code:
import functools
import operator
 
number = int(input())
xdn_list = []
for i in range(number):
    xdn = input().split()
    xdn_list.append(xdn)
    
for j in xdn_list:
    answer = []
    for k in range(int(j[2])):
        answer.append(int(j[0])+int(j[1])* k)
    result = functools.reduce(operator.mul, answer)
    print(answer)
    print(result%1000003)

Submission status: Wrong Answer

Solution code:
p=1000003
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,p)[0]%p
def exponen(a,b):
    if b==0:
        return 1
    elif b%2==0:
        return exponen((a*a)%p,b//2)
    else:
        return (a*exponen((a*a)%p,b//2))%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:
Q = int(input())
x = [0] * Q
d = [0] * Q
n = [0] * Q

for i in range(Q):
	x[i], d[i], n[i] = map(int, input().split())
	numberToBeDivided = x[i]
	for j in range(1, n[i]):
		numberToBeDivided *= d[i]*j
	print(numberToBeDivided%1000003)

Submission status: Wrong Answer

Solution code:
Q = int(input())

a = [[int(i) for i in input().split()] for j in range(Q)]

for i in range(Q):
    m = a[i][0]
    for j in range(a[i][2]-1):
        m *= (a[i][0]+(j+1)*a[i][1])%1000003
    print(m)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
Q = int(input())
for i in range(Q):
  x,d,n = map(int,input().split())
  K = 1
  for j in range(n):
    K *= x+d*i
  H = K//1000003
  print(H)

Submission status: Wrong Answer

Solution code:
def compute(x,d,n):
  prod = x
  mod = 1000003
  for i in range(1,n):
    prod = prod*(n+i*d)
    prod = prod%mod
  return prod
    
q = int(input())
for i in range(q):
  x,d,n = map(int,input().split())
  print(compute(x,d,n))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
while(t):
    pro=1
    x,d,n=map(int,input().strip().split())
    for i in range(1,n+1):
        a=x+(i-1)*d
        pro*=a
    print(pro%1000003)
    t-=1

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 6 + 3

#TLE
def solve():
    x, d, n = map(int, input().split())
    ans = 1
    for i in range(n):
        ans *= (x+i*d)
        ans %= mod
    print(ans)
    return


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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 *= p
    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 _ in range(mod+1)]
invf = [1 for _ in range(mod+1)]
invf[mod] = 0
for i in range(mod):
  frac[i+1] = (frac[i] * (i+1)) % mod
invf[mod-1] = inved(frac[mod-1])
for i in range(mod-1, 0, -1):
  invf[i-1] = (invf[i] * i) % 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] * invf[xinvd]) % mod)

Submission status: Time Limit Exceeded

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 *= p
    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: Time Limit Exceeded

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(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: Time Limit Exceeded

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) - 1
        xinvd %= mod
        print((dn * frac[xinvd + n] * inved(frac[xinvd])) % mod)

Submission status: Time Limit Exceeded

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
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 * doubling(d, mod - 2) - 1
        xinvd %= mod
        print((dn * frac[xinvd + n] * doubling(frac[xinvd], mod - 2)) % mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**6+3

def main():
    # preprocess
    fac = [1, 1]
    f_inv = [1, 1]
    inv = [0, 1]

    for i in range(2, MOD+1):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

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

        if d == 0:
            print(pow(x, n, MOD))
            continue
        
        xd = ((x % MOD) * pow(d, MOD-2, MOD)) % MOD
        if xd == 0 or xd + (n-1) >= MOD:
            print(0)
            continue

        print(pow(d, n, MOD) * fac[xd+(n-1)] * f_inv[xd - 1] % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
for a0 in range(int(input())):
  a,b,c=list(map(int, input().split()))
  prod=1
  for i in range(c):
    prod*=(a%1000003)
    a+=(b%1000003)
  print(prod%1000003)

Submission status: Time Limit Exceeded

Solution code:
p = 10**6+3
Q = int(input())
for _ in range(Q):
    x,d,n = map(int,input().split())
    if x==0 or n>=p:
        print(0)
    else:
        tot = x
        for i in range(1,n):
            if (x+i*d)%p==0:
                tot = 0
                break
            tot = (tot*((x+i*d)%p))%p
        print(tot)

Submission status: Time Limit Exceeded

Solution code:
p = 10**6+3
Q = int(input())
for _ in range(Q):
    x,d,n = map(int,input().split())
    prod = 1
    for i in range(p):
        prod = (prod*((x+i*d)%p))%p
    k = n//p
    m = n%p
    prod1 = 1
    for i in range(k):
        prod1 = (prod1*prod)%p
    prod2 = 1
    for i in range(m):
        prod2 = (prod2*((x+i*d)%p))%p
    print((prod1*prod2)%p)

Submission status: Time Limit Exceeded

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())
  print(((d**n)*F[(x*pow(d,mod-2,mod)+n-1)%mod]*FI[(x*pow(d,mod-2,mod)-1)%mod])%mod)

Submission status: Time Limit Exceeded

Solution code:
# MERGE IT


'''n=int(input())
for i in range(0,n):
    o=int(input())
    p=input().rstrip().split(' ')
    l=[0]*3;
    for j in range(0,len(p)):
        l[(int(p[j])%3)]+=1;
    s=0;
    s+=l[0];
    s+=min(l[1],l[2])
    if min(l[1],l[2])==l[2]:
        l[1]-=l[2]
        s+=(l[1]//3)
    elif min(l[1],l[2])==l[1]:
        l[2]-=l[1]
        s+=(l[2]//3)
    print(s)'''

# LOSE IT

n=int(input())
for i in range(0,n):
    F=1;
    p=input().rstrip().split(' ')
    for j in range(0,int(p[2])):
        if j==0:
            F=F*int(p[0])
        else:
            F=(F*(int(p[0])+int(p[1])))%1000003
            p[0]=int(p[0])+int(p[1])
    print(F%1000003)

Submission status: Time Limit Exceeded

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)