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

Solution code:
mod = 10**6 + 3

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

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)/b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def inverse(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

def mod_pow(x, n, mod):
    ret = 1
    while n > 0:
        if n & 1 != 0:
            ret *= x
        x *= x
        n >>= 1
    return ret

l = raw_input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = raw_input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(mod_pow(x, n, mod))
        continue
    inv_d = inverse(d, mod)
    x_d = (x * inv_d) % mod
    d_n = mod_pow(d, n, mod)
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1, d_n)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[(x_d + n - 1) % mod]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * inverse(ans2, mod)
    ans %= mod
    ans = ans * d_n
    ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**6 + 3

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

def gcd(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)/b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def inverse(n, mod):
    table = gcd(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

l = raw_input().split()
Q = int(l[0])
X = []
D = []
N = []
for i in range(Q):
    l = raw_input().split()
    X.append(int(l[0]))
    D.append(int(l[1]))
    N.append(int(l[2]))


for i in range(Q):
    x = X[i]
    d = D[i]
    n = N[i]
    if d == 0:
        print(x**n)
        continue
    inv_d = inverse(d, mod)
    x_d = (x * inv_d) % mod
    d_n = (d**n) % mod
    # print(i, x, d, n, inv_d, x_d, x_d + n - 1, d_n)
    if x_d + n - 1 >= mod:
        print(0)
        continue
    ans1 = fac[(x_d + n - 1) % mod]
    ans2 = fac[x_d - 1]
    # print(ans1, ans2)
    ans = ans1 * inverse(ans2, mod)
    ans %= mod
    ans = ans * d_n
    ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

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)

print(sol())

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

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

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def rpow(x,e,r):
    p = 1
    while e>0:
        if e%2 == 1:
            p = (p*x)%r
        x *= x
        e //= 2
    return p

R = 1000003
facts = [1] * R
for i in range(2,R):
    facts[i] = (facts[i-1]*i)%R

qq = inn()
for q in range(qq):
    x,d,n = inm()
    if d==0:
        print(rpow(x,n,R))
        continue
    xd = modinv(d,R)
    y = (x * xd) % R
    if y+n-1 >= R:
        print(0)
    else:
        z = rpow(d,n,R) * facts[y+n-1] * modinv(facts[y-1],R)
        print(z%R)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

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

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

# combinatorial(n,k) mod r
def comb(p,q,r):
    if q==0 or q==p:
        return 1
    if q > p-q:
        q = p-q
    num = p
    den = q
    for i in range(1,q):
        num = (num * (p-i))%r
        den = (den * (q-i))%r
    xden = modinv(den,r)
    return (num*xden)%r

def rpow(x,e,r):
    p = 1
    while e>0:
        if e%2 == 1:
            p = (p*x)%r
        x *= x
        e //= 2
    return p

R = 1000003
facts = [1] * R
for i in range(2,R):
    facts[i] = (facts[i-1]*i)%R
ddprint(facts[:33])

qq = inn()
for q in range(qq):
    x,d,n = inm()
    if d==0:
        print(rpow(x,n,R))
        continue
    xd = modinv(d,R)
    y = (x * xd) % R
    ddprint("x {} d {} n {} xd {} y {}".format(x,d,n,xd,y))
    if y+n-1 >= R:
        print(0)
    else:
        z = rpow(d,n,R) * facts[y+n-1] * modinv(facts[y-1],R)
        print(z%R)

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

Max = mod-1
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod
def pow_mod(x,n):
    if n==0: return 1
    if n%2:return x*pow_mod(x,n-1)%mod
    a = pow_mod(x,n//2)
    return a*a%mod

Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow_mod(x,n)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))

Submission status: Time Limit Exceeded

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

Max = mod-1
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod
def pow_mod(x,n):
    if n==0: return 1
    if n%2:return x*pow_mod(x,n-1)%mod
    a = pow_mod(x,n//2)
    return a*a%mod

Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow_mod(x,n)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = []
for i in range(N):
    x,d,n = map(int, input().split())
    p = 1
    for j in range(1, n + 1):
        m = x + (d * (j - 1))
        p *= m
    ans.append(p%(10**6+3))
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

#C
def C():
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    s = f[0][1]
    c = LI()
    c.sort(key = lambda x:-x)
    f[0][0] = c[0]
    q = deque()
    q.append(s)
    bfs = [1 for i in range(n)]
    f.sort(key = lambda x:x[1])
    bfs[s] = 0
    k = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                f[y][0] = c[k]
                k += 1
                q.append(y)
    ans = 0
    q.append(s)
    bfs = [1 for i in range(n)]
    bfs[s] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    mod = 1000003
    q = I()
    for _ in range(q):
        x,d,n = LI()
        if x == 0:
            print(0)
        elif d == 0:
            print(pow(x,n,mod))
        s = x
        for i in range(1,n):
            s *= (x+d*i)
            s %= mod
            if s == 0:
                print(0)
                break
        else:
            print(s)
    return

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

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

Submission status: Time Limit Exceeded

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)
        ans %= 1000003
    anss.append(ans)

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

Submission status: Time Limit Exceeded

Solution code:
Q=int(input())

for i in range(Q):
    result=1
    x,d,n=map(int,input().split())
    for j in range(n):
        if x+j*d>1000003:
            result=result*(x+j*d)%1000003
        else:
            result=result*(x+j*d)
    print(result%1000003)

Submission status: Time Limit Exceeded

Solution code:
def factorial(a,d,n,mod):
	ans=1
	for i in xrange(n-1):
		ans=(ans*(a+i*d))%mod
	return ans



q=int(raw_input())
mod=1000003

for i in xrange(q):
	x,d,n=map(int,raw_input().split())
	print (x*factorial(x+d,d,n,mod))%mod

Submission status: Time Limit Exceeded

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)
    ans %= 1000003
    anss.append(ans)

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

Submission status: Time Limit Exceeded

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(result%1000003)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
XDN = [tuple(map(int,input().split())) for _ in range(Q)]
mod = 1000003

for i in range(Q):
    ans = 1
    j = 0
    a = XDN[i][0]
    for _ in range(XDN[i][2]):
        b = a % mod
        ans = (ans * b) % mod
        a += XDN[i][1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

Q = int(input())

l = deque()
for _ in range(Q):
    x, d, n = map(int, input().split())
    l.append((x, d, n))

for x, d, n in l:
    if n >= 1000003:
        print(0)
        continue
    I = 0
    for i in range(min(d, 1000003-d)):
        div, mod =divmod((1000003 * (i+1)) - x, d)
        if mod == 0:
            I += div
            break
        else:
            I += (1000003 // d) + 1
    num = 1
    for i in range(min(I, n)):
        num *= divmod(x + i*d, 1000003)[1]
        num = divmod(num, 1000003)[1]
        if num == 0:
            break
    print(num)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    mod = 10 ** 6 + 3
    num = int(input())
    for _ in range(num):
        x, d, n = map(int, input().split())
        if x == 0:
            print(0)
            continue
        ans = 1
        kari = x
        for i in range(n):
            ans *= kari
            kari += d
            ans %= mod
        print(ans % mod)



if __name__ == '__main__':
    main()
    # mod = 10 ** 9 + 7
    # print((71 * 312500008) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter as D, defaultdict as dd
from math import factorial as ft, ceil as aron
from fractions import gcd as pg 

f1=lambda : map(int,raw_input().split())
f2=lambda : map(int,list(raw_input()))
f3=lambda : int(raw_input())
f4=lambda : raw_input().rstrip()


def factorial(a,d,n,mod):
	ans=1
	for i in xrange(n-1):
		ans=(ans*(a+i*d))%mod
	return ans



q=int(raw_input())
mod=1000003

for i in xrange(q):
	x,d,n=map(int,raw_input().split())
	print (x*factorial(x+d,d,n,mod))%mod

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

Q = int(input())
a = []
def tosa(x, d, n):
	array = []
	array.append(x%1000003)
	for i in range(n-1):
		x = (x + d)%1000003
		array.append(x)
	return array
for _ in range(Q):
	a.append(list(map(int, input().split())))

for i in range(Q):
	seki = tosa(a[i][0], a[i][1], a[i][2])
	ans = 1
	for j in seki:
		ans = (ans * j)%1000003
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
xdn = [list(map(int, input().split())) for i in range(q)]
for i in xdn:
  answer = 1
  x = i[0]
  for j in range(i[2]):
    answer = answer * x % 1000003
    if answer == 1:
      x = i[0]
      for k in range(i[2] % j):
        answer = answer * x % 1000003
        x = x + i[1] % 1000003
      break
    else:
      x = x + i[1] % 1000003
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

#C
def C():
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    s = f[0][1]
    c = LI()
    c.sort(key = lambda x:-x)
    f[0][0] = c[0]
    q = deque()
    q.append(s)
    bfs = [1 for i in range(n)]
    f.sort(key = lambda x:x[1])
    bfs[s] = 0
    k = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                f[y][0] = c[k]
                k += 1
                q.append(y)
    ans = 0
    q.append(s)
    bfs = [1 for i in range(n)]
    bfs[s] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    mod = 1000003
    def f(x,n,d):
        if s[(x,n,d)] != None:
            return s[(x,n,d)]
        if n == 1:
            s[(x,n,d)] = x%mod
            return x
        s[(x,n,d)] = f(x,n//2,d)*f(x+n//2*d,(n+1)//2,d)%mod
        return s[(x,n,d)]
    s = defaultdict(lambda: None)

    q = I()
    for i in range(q):
        x,d,n = LI()
        if d == 0:
            print(pow(x,n,mod))
        elif n >= mod:
            print(0)
        else:
            print(f(x,n,d))
    return

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
for z in range(n):
  op=1
  x,d,m=input().split(' ')
  a=int(x)
  d=int(d)
  m=int(m)
  for m in range(m):
    op=(op*a)%1000003
    a+=d
  print(op)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

mod = 1000003

def prod(x, y):
    return (x * y) % 1000003


def main():
    q = int(input())

    for i in range(q):
        x, d, n = map(int, input().split())
        arr = [x + i * d for i in range(n)]
        print(reduce(prod, arr))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
q=int(input())
xdn=[]
nans=0
for i in range(q):
    xdn.append(list(map(int,input().split())))
    sn=xdn[i][0]
    ans=xdn[i][0]
    for _ in range(xdn[i][2]-1):
        sn+=xdn[i][1]
        ans*=sn
        nans=ans%1000003
    print(nans)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
for i in range(Q):
    x,d,n = map(int,input().split())
    a = n // 1000003
    b = n % 1000003
    q = 1
    if a >= 1:
        for j in range(1000003):
            q = q * (x + j*d) % 1000003
    r = q
    for i in range(a):
        q = q * r % 1000003
    for k in range(b):
        q = q * (x + k * d) % 1000003
    print(q)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

mod = 1000003

def mpow(x, n):
  ans = 1
  while n != 0:
    if n&1:
      ans = ans * x % mod
    x = x * x % mod
    n = n // 2
  return ans

def mprod(xs):
  ans = 1
  for x in xs:
    ans = (ans * x) % mod
  return ans



for qq in range(q):
  x, d, n = map(int, input().split())
  #print(x, d, n)
  i = 0
  cycle = []
  found = [0 for i in range(mod)]
  # find cycle
  prod_cycle = 1
  xx = x-d
  while True:
    xx = (xx + d) % mod
    if found[xx] == 1:
      break
    prod_cycle = (prod_cycle * xx) % mod
    cycle.append(xx)
    found[xx] = 1

    i += 1
    if i == n:
      break

  #print(f'cycle len={len(cycle)}')
  if i != n:
    num_cycles = n // len(cycle)
    #prod_cycle = mprod(cycle)
    #print(f'calculated product of cycle')
    p = mpow(prod_cycle, num_cycles)
    #print(f'calculated fast power')
    remainings = n % len(cycle)
    prod_remainings = mprod(cycle[0:remainings])
    #print(f'calculated remaining product')
    pp = (p * prod_remainings) % mod
    #print(f'calculated final answer')
    print(pp)
  else:
    print(mprod(cycle))

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
xdn = [list(map(int, input().split())) for i in range(q)]
for i in xdn:
  answer = 1
  x = i[0]
  for j in range(i[2]):
    answer = answer * x % 1000003
    x = x + i[1] % 1000003
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
q = 1000003
N = int(input())
queries = [list(map(int, input().split())) for _ in range(N)]
for x, d, n in queries:
    prod = 1
    ans = reduce(lambda prod, next: prod * next % q, [x + i*d for i in range(n)], prod)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
for x in range(n):
  op=1
  x,d,n=input().split(' ')
  a=int(x)
  for m in range(int(n)):
    op=(op*a)%1000003
    a+=int(d)
  print(op)

Submission status: Time Limit Exceeded

Solution code:
def ans():
    x ,d ,n = map(int,input().split())
    return  list_(x,d,n) % 1000003

def list_(x ,d ,n):
        ans = 1
        for i in [x + j*d for j in range(n)]:
            ans = ans * i
        return ans

Q = int(input())
[print(i) for i in [ans() for i in range(Q)]]

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

Q = int(input())
a = []
def tosa(x, d, n):
	array = []
	array.append(x)
	for i in range(n-1):
		x = x + d
		array.append(x)
	return array
for _ in range(Q):
	a.append(list(map(int, input().split())))

for i in range(Q):
	seki = tosa(a[i][0], a[i][1], a[i][2])
	ans = 1
	for j in seki:
		ans = (ans * j)%1000003
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

x_list = []
d_list = []
n_list = []

for i in range(N):
    x, d, n = list(map(int, input().split()))
    x_list.append(x)
    d_list.append(d)
    n_list.append(n)


for x, d, n in zip(x_list, d_list, n_list):
    new_x = x + d
    answer = x
    answer_1 = 1
    answer_2 = 1
    memo_list = []
    if n % 2 == 0:
        for i in range(0, int(n / 2), 2):
            if d * i not in memo_list:
                answer_1 = answer_1 * (d * (i) + x)
                memo_list.append(d * i)
            if d * (i + 1) not in memo_list:
                answer_1 = answer_1 * (d * (i + 1) + x)
                memo_list.append(d * (i + 1))
            if (n - i - 1) * d not in memo_list:
                 answer_2 = answer_2 * ((n - i - 1) * d + x)
                 memo_list.append(d * (n - i - 1))
            if (n - i - 2) * d not in memo_list:
                answer_2 = answer_2 * ((n - i - 2) * d + x)
                memo_list.append(d * (n - i - 2))
    else:
        for i in range(0, int(n / 2) + 1, 2):
            if d * i not in memo_list:
                answer_1 = answer_1 * (d * (i) + x)
                memo_list.append(d * i)
            if d * (i + 1) not in memo_list:
                answer_1 = answer_1 * (d * (i + 1) + x)
                memo_list.append(d * (i + 1))
            if (n - i - 1) * d not in memo_list:
                answer_2 = answer_2 * ((n - i - 1) * d + x)
                memo_list.append(d * (n - i - 1))
            if (n - i - 2) * d not in memo_list:
                answer_2 = answer_2 * ((n - i - 2) * d + x)
                memo_list.append(d * (n - i - 2))

    print(answer_1 * answer_2 % 1000003)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

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

Submission status: Time Limit Exceeded

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

Q = int(input())
for i in range(Q):
  cross=1
  x, d, n = (int(j) for j in input().split()) 
  for j  in range(n):
    cross=cross*(x+d*j)
  print(cross%1000003)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
for x in range(n):
  op=1
  x,d,n=input().split(' ')
  a=int(x)
  for m in range(int(n)):
    op=op*a
    a+=int(d)
  print(op%1000003)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
mod = 1000003

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

    cnt = 1

    for j in range(n):
        cnt *= (x + j * d)
        cnt %= mod

    print(cnt % mod)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())

mod = 1000003

def mpow(x, n):
  ans = 1
  while n != 0:
    if n&1:
      ans = ans * x % mod
    x = x * x % mod
    n = n // 2
  return ans

def mprod(xs):
  ans = 1
  for x in xs:
    ans = (ans * x) % mod
  return ans



for qq in range(q):
  x, d, n = map(int, input().split())
  #print(x, d, n)
  i = 0
  cycle = []
  found = {}
  # find cycle
  while True:
    xx = (x + d * i) % mod
    if xx in found:
      break
    cycle.append(xx)
    found[xx] = True

    i += 1
    if i == n:
      break

  #print(f'cycle len={len(cycle)}')
  if i != n:
    num_cycles = n // len(cycle)
    prod_cycle = mprod(cycle)
    p = mpow(prod_cycle, num_cycles)
    remainings = n % len(cycle)
    prod_remainings = mprod(cycle[0:remainings])
    pp = (p * prod_remainings) % mod
    print(pp)
  else:
    print(mprod(cycle))

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
sub = 1000003
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: Time Limit Exceeded

Solution code:
def pochh2(x,d,n):
    ans=1
    for i in range(n):
        ans=ans*(x+i*d)
    return ans

Q=int(input())
for i in range(Q):
    a,b,c = map(int, input().split())
    print(pochh2(a,b,c)%1000003)

Submission status: Time Limit Exceeded

Solution code:
q = int(input())
mod = 1000003

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

    cnt = 1

    for j in range(n):
        cnt *= (x + j * d)

    print(cnt % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 int(input())
from collections import defaultdict

def calc(x, d, n):
    ans = 1
    for i in range(n):
        ans = ans * (x + i * d)
        ans = ans % 1000003
    return ans

q = SI()
ans = []
for i in range(q):
    x, d, n = LI()
    ans.append(calc(x, d, n))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
Q = int(input())
k = 10**6+3
for _ in range(Q):
  x,d,n = map(int,sys.stdin.readline().split())
  ans = 1
  count = x
  for i in range(n):
    ans = ans*count%k
    count += d
  print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Solution code:
Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
import math

Q = int(input())

l = []
for _ in range(Q):
    x, d, n = map(int, input().split())
    l.append((x, d, n))

for x, d, n in l:
    if n >= 1000003:
        print(0)
        continue
    num = 1
    for i in range(n):
        num *= divmod(x + i*d, 1000003)[1]
        num = divmod(num, 1000003)[1]
    print(num)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())
for i in range(Q):
    x, d, n = list(map(int, input().split()))
    X = [x + (n-i-1)*d for i in range(n)]
    res = 1
    for x in X:
        res *= x
        res = res%1000003
    print(res)

Submission status: Time Limit Exceeded

Solution code:
Q = int(input())

ans = [0 for i in range(Q)]

lim = 1000003

for i in range(Q):
    x, d, n = map(int, input().split())
    tmp = 1
    for j in range(1, n+1):
        tmp *= (x + (j-1)*d)
        if tmp > lim:
            tmp = tmp % lim
    ans[i] = tmp

for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(1000000)

q = int(input())

@lru_cache(maxsize=None)
def prod(m, d, n):
  if (n == 0):
    return 1
  elif (n == 1):
    return m
  else:
    m2 = (m + d * (n // 2)) % 1000003
    return prod(m , d, (n // 2)) * prod(m2, d, n - (n // 2))

for i in range(q):
  x1, d1, n1 =[int(j) for j in input().split()]
  p = prod(x1, d1, n1)
  p = p % 1000003
  print (p)