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:
Q = int(input())

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

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

		if xi // 1000003 >= 1:
			xi = xi % 1000003

		ans *= xi

		if ans // 1000003 >= 1:
			ans = ans % 1000003

	print(ans)

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(1, n+1):
        term = x + (j-1) * d
        result *= term
    print(result % 1000003)

Submission status: Time Limit Exceeded

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

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 *= x
        x += d
    print("{}".format(ans % 1000003))

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 *= x + j * d

	ans = ans % 1000003

	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 *= (x + j * d)
    print(ans % 1000003)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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

Submission status: Accepted

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

Solution code:
mod=1000003
fact=[1]
for i in range(1,2*mod):
  fact.append((fact[-1]*i)%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 n>=mod or x==0:
    print(0)
    continue
  x*=pow(d,mod-2,mod)
  x%=mod
  ans=fact[x+n-1]*pow(fact[x-1],mod-2,mod)*pow(d,n,mod)
  ans%=mod
  print(ans)

Submission status: Accepted

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:
        print(pow(x,n,mod))
        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: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())

M = 1000003 # 出力の制限
N = 10**6+20 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

def sub(x, n):
#     print(x, n)
    if x+n-1>=M:
        ans = 0
    else:
        if x>=1:
            ans = g1[x+n-1]*g2[x-1]
        else:
            ans = g1[x+n-1]
    return ans
ans = [None]*q
for i in range(q):
    x,d,n = list(map(int, input().split()))
    if d>=1:
        xd = (x * inverse[d]) % M
        ans[i] = (sub(xd, n) * pow(d, n, M)) % M
    else:
        ans[i] = pow(x, n, M)
write("\n".join(map(str, ans)))

Submission status: Accepted

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):
    if(d==0):
        return pow(x,n,mod)
    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: Accepted

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

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(x, 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: Accepted

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 x == 0:
        return 0

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

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

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())
  if d == 0:
    print(pow(x, n, mod))
    continue
  z = -x * pow(d, mod - 2, mod) % mod
  v = -z % mod
  #print(z, v, (x + z * d) % mod)
  if z < n:
    print(0)
    continue
  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: Accepted

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 d==0:
        print(pow(x,n,mod))
    elif 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: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

md=10**6+3
n_max = md-1
fac = [1]
for i in range(1, n_max + 1): fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1) % md

def main():
    for _ in range(II()):
        x,d,n=MI()
        if x==0:ans=0
        elif d==0:ans=pow(x,n,md)
        else:
            invd=pow(d,md-2,md)
            x=x*invd%md
            if x+n-1>=md:ans=0
            else:
                ans=fac[x+n-1]*ifac[x-1]*pow(d,n,md)%md
        print(ans)

main()

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

q = int(input())
info = [list(map(int, input().split())) for i in range(q)]
MOD = 1000003
comb = Combination(MOD, MOD)

for x, d, n in info:
    if d == 0:
        ans = pow(x, n, MOD)
        print(ans)
        continue

    ans = pow(d, n, MOD)
    x_d = x * pow(d, MOD - 2, MOD) % MOD
    
    # x_d * (x_d + 1) * (x_d + 2) * ... *(x_d + n - 1)
    tmp = comb.factorial(min(x_d + n - 1, MOD)) * pow(comb.factorial(x_d - 1), MOD - 2, MOD)
    ans *= tmp
    print(ans % MOD)

Submission status: Accepted

Solution code:
from math import factorial

q = int(input())
mod = 1000003

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


def query():
    x, d, n = map(int, input().split())
    if d == 0:
        return pow(x, n, mod)
    first = (x * pow(d, mod - 2, mod)) % mod
    if first + n - 1 >= mod:
        return 0
    return (fact[first + n - 1] * pow(fact[first - 1], mod - 2, mod) * pow(d, n, mod)) % mod


print("\n".join([str(query()) for i in range(q)]))

Submission status: Accepted

Solution code:
MOD = 1000003
fac = [1] * (10 ** 6 * 3)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
q = int(input())
for _ in range(q):
    x, d, n = map(int, input().split())
    if x == 0:
        print(0)
    elif d == 0:
        print(pow(x, n, MOD))
    elif n >= MOD:
        print(0)
    else:
        x = x * pow(d, MOD - 2, MOD) % MOD
        print(fac[x + n - 1] * pow(fac[x - 1], MOD - 2, MOD)
              * pow(d, n, MOD) % MOD)

Submission status: Accepted

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

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 d == 0:
        ans = pow(x, n, mod)
    elif 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: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
# MOD = 10 ** 9 + 7
# MOD = 998244353

MOD = 1000003

Q = int(sys.stdin.buffer.readline())
XDN = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


factorials = get_factorials(MOD, MOD)
invs = mod_invs(MOD, MOD)
finvs = factorial_invs(MOD, MOD)


def solve(args):
    x, d, n = args
    if d == 0:
        return pow(x, n, MOD)
    num = x * invs[d] % MOD + n - 1
    if num >= MOD:
        return 0
    return pow(d, n, MOD) * factorials[num] % MOD * finvs[(x * invs[d] - 1) % MOD] % MOD


print(*map(solve, XDN), sep='\n')

Submission status: Accepted

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



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

Solution code:
# E - Product of Arithmetic Progression

import sys
input = sys.stdin.buffer.readline

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

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

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

def factorial(x, p=MOD):
    if x < p:
        return factorial_memo[x]
    else:
        return 0


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

Submission status: Accepted

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

Solution code:
mod=10**6+3
P=[0 for i in range(mod)]
P[0]=1
for i in range(0,len(P)-1):
    P[i+1]=(P[i]*(i+1))%mod
P[0]=0
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    if d>0:
        D=pow(d,mod-2,mod)
        L=x*D%mod
        if L+n-1<mod:
            if L>0:
                value=P[L+n-1]*pow(P[L-1],mod-2,mod)*pow(d,n,mod)
            else:
                value=P[L+n-1]*pow(d,n,mod)
            print(value%mod)
        else:
            print(0)
    else:
        print(pow(x,n,mod))

Submission status: Accepted

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())
    if d>0:
        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)
    else:
        print(pow(x,n,mod))

Submission status: Accepted

Solution code:
import sys

def main():
    MOD = 10**6+3

    # preprocess
    fac = [None] * (MOD+1)
    fac[0] = fac[1] = 1
    for i in range(2, MOD+1):
        fac[i] = (fac[i-1] * i) % MOD

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

        if d == 0:
            print(pow(x, n, MOD))
            continue
        
        xd = (x * 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)] * pow(fac[xd-1], MOD-2, MOD) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
####################
#  AC:     ms (PyPy)
####################

def main():
    MOD = 10**6+3
    # preprocess
    fac = [None] * (MOD+1)
    fac[0] = fac[1] = 1
    for i in range(2, MOD+1):
        fac[i] = (fac[i-1] * i) % MOD

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

        if x == 0:
            print(0)
            continue

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
####################
#  AC:     ms (PyPy)
####################

def main():
    MOD = 10**6+3
    # preprocess
    fac = [None] * (MOD+1)
    fac[0] = fac[1] = 1
    for i in range(2, MOD+1):
        fac[i] = (fac[i-1] * i) % 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 * 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)] * pow(fac[xd-1], MOD-2, MOD) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**6+3

def main():
    # preprocess
    fac = [None] * (MOD+1)
    fac[0] = fac[1] = 1
    for i in range(2, MOD+1):
        fac[i] = (fac[i-1] * i) % 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 * 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)] * pow(fac[xd-1], MOD-2, MOD) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD = 10**6+3

def main():
    # preprocess
    fac = [1, 1]
    for i in range(2, MOD+1):
        fac.append((fac[-1] * i) % 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 * 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)] * pow(fac[xd-1], MOD-2, MOD) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Solution code:
mod=10**6+3

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

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

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

for x,d,n in xdn:
    if d==0:
        print(pow(x,n,mod))
        continue
    if x==0:
        print(0)
        continue
    k=x*inv[d]%mod
    if k+n-1>=mod:
        print(0)
    else:
        print(pow(d,k+n-1,mod)*data[k+n-1]*inv[pow(d,k-1,mod)*data[k-1]%mod]%mod)

Submission status: Accepted

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

main()

Submission status: Accepted

Solution code:

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]
    mod = 10 ** 6 + 3

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

    for i in range(num):
        x, d, n = data[i]
        if d == 0:
            ans = pow(x, n, mod)
        else:
            t = x * pow(d, mod - 2, mod)
            t %= mod
            if t == 0 or t + n - 1 >= mod:
                ans = 0
            else:
                ans = origin[t + n - 1] * pow(origin[t - 1], mod - 2, mod)
                ans %= mod
                ans *= pow(d, n, mod)
                ans %= mod
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000003
MAX = MOD + 2
fac, finv, inv = [], [], []

def initCombTable():
  fac.append(1)
  fac.append(1)
  finv.append(1)
  finv.append(1)
  inv.append(0)
  inv.append(1)
  for i in range(2, MAX):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)


def main():
  initCombTable()
  q = int(input())
  for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
      print(pow(x, n, MOD))
    else:
      xd = x * pow(d, MOD-2, MOD) % MOD
      if xd+n-1>=MOD or xd == 0:
        print(0)
      else:
        ans = fac[xd+n-1] * finv[xd-1] % MOD
        ans = ans * pow(d, n, MOD) % MOD
        print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
q=int(input())
m=10**6+3
f=[1]
for i in range(1,m):
    f.append(f[-1]*i%m)
for i in range(q):
    x,d,n=map(int,input().split())
    if d==0:
        print(pow(x,n,m))
    else:
        t=x*pow(d,m-2,m)%m
        if t==0 or t+n-1>=m:
            print(0)
        else:
            print(f[t+n-1]*pow(f[t-1],m-2,m)*pow(d,n,m)%m)

Submission status: Accepted

Solution code:
MOD = 1000003
facts = [1,1] #階乗
for ind in range(1, MOD):
    i = ind+1
    facts.append(facts[-1]*i % MOD)

def invmod(x, MOD=MOD):
    return pow(x, MOD-2, MOD)

def task(x, d, n, MOD=MOD):
    if x == 0:
        return 0
    if d == 0:
        return pow(x, n, MOD)
    
    xdivd = (x*invmod(d)) % MOD
    if MOD <= xdivd + n -1:
        return 0
    ans = (facts[xdivd + n -1]*invmod(facts[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)

Submission status: Accepted

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

Submission status: Accepted

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