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

Solution code:
M=1000003
f=[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):
	x,d,n=map(int,input().split())
	t=x*pow(d,M-2,M)%M
	if d==0:
		print(pow(x,n,M))
	elif t==0 or t+n>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:
M=1000003
f=[1]
for i in range(1,M):
	f.append(f[i-1]*i%M)
Q=int(input())
for _ in'_'*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 = 10 ** 6 + 3

W = [1] * (mod)
for i in range(mod - 1):
	W[i + 1] = ((i + 1) * W[i]) % mod

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

def f(x, d, n):
	if d == 0:
		return pow(x, n, mod)
	else:
		d_r = rev(d)
		xdr = d_r * x % mod
		if xdr == 0:
			return 0
		elif (xdr + n - 1) >= mod:
			return 0
		else:
			return (W[xdr + n - 1] * rev(W[xdr - 1]) % mod) * pow(d, n, mod) % mod

ans = []
q = int(input())
for _ in range(q):
    x,d,n = map(int,input().split())
    ans.append(f(x,d,n))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
mod = 10 ** 6 + 3

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

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

def f(x, d, n):
	if d == 0:
		return pow(x, n, mod)
	else:
		d_r = rev(d)
		xdr = d_r * x % mod
		if xdr == 0:
			return 0
		elif (xdr + n - 1) >= mod:
			return 0
		else:
			return (W[xdr + n - 1] * rev(W[xdr - 1]) % mod) * pow(d, n, mod) % mod

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

Submission status: Accepted

Solution code:
mod = 10 ** 6 + 3

W = [1] * (mod)
for i in range(mod - 1):
	W[i + 1] = ((i + 1) * W[i]) % mod

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

def f(x, d, n):
	if d == 0:
		return pow(x, n, mod)
	else:
		d_r = rev(d)
		xdr = d_r * x % mod
		if xdr == 0:
			return 0
		elif (xdr + n - 1) >= mod:
			return 0
		else:
			return (W[xdr + n - 1] * rev(W[xdr - 1]) % mod) * pow(d, n, mod) % mod

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

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**6 + 3

    factrial = [1] * (MOD)
    for k in range(1, MOD):
        factrial[k] = (factrial[k-1] * k) % MOD
    
    fact_inv = [1] * (MOD)
    fact_inv[MOD-1] = pow(factrial[MOD-1], MOD - 2, MOD)
    for k in range(MOD-2, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

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

        if d == 0:
            ans = pow(x, n, MOD)

        else:
            y = x * pow(d, MOD-2, MOD) % MOD

            if y + n - 1 >= MOD:
                ans = 0

            else:
                ans = (factrial[y+n-1] * fact_inv[y-1] * pow(d, n, MOD)) % MOD

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 6 + 3

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

fact, inv = init_fact_inv(MOD, MOD)

Q=INT()
for i in range(Q):
    x,d,n=MAP()

    # 例外処理
    if x==0:
        print(0)
        continue
    if d==0:
        print(pow(x, n, MOD))
        continue
    
    invd=pow(d, MOD-2, MOD)
    l=(x*invd-1)%MOD
    r=l+n

    # 例外処理
    if r>=MOD:
        print(0)
        continue

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def PoAP_fnct(MOD):
    #MOD:素数
    fact_mod = [1,1]
    inv_mod = [0,1]
    inv_fact_mod = [1,1]
    i = len(fact_mod)
    i_ = len(inv_fact_mod)

    def PoAP(x,d,n):
        nonlocal i, i_
        if d == 0:
            return pow(x,n%(MOD-1),MOD)

        while d >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        j = (-x*inv_mod[d])%MOD
        if j < n:
            return 0

        x = (x*inv_mod[d])%MOD

        while (x+n-1)%MOD >= i:
            fact_mod[i:i] = [(fact_mod[i-1]*i)%MOD]
            i += 1

        while x-1 >= i_:
            inv_mod[i_:i_] = [(-inv_mod[MOD%i_]*(MOD//i_))%MOD]
            inv_fact_mod[i_:i_] = [(inv_fact_mod[i_-1]*inv_mod[i_])%MOD]
            i_ += 1

        return fact_mod[(x+n-1)%MOD] * inv_fact_mod[x-1] * pow(d,n%(MOD-1),MOD) % MOD
    return PoAP

def solve():
    Q = int(input())
    PoAP = PoAP_fnct(1000003)
    res = '\n'.join([str(PoAP(*map(int, input().split()))) for _ in range(Q)])
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**6+3
q = int(input())

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**6+3
q = int(input())

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

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:
            if x_div+n-1 >= MOD:
                ans = 0
            else:
                f = fact[x_div+n-1]
                fi = pow(fact[x_div-1], MOD-2, MOD)
                ans = f*fi%MOD*pow(d, n, MOD)%MOD
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
MOD = 10**6+3
q = int(input())

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

for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        ans = pow(x, n, MOD)
    else:
        x_div = x*pow(d, MOD-2, MOD)%MOD
        if x_div+n-1 > MOD:
            ans = 0
        else:

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

Submission status: Accepted

Solution code:
q = int(input())
Q = [[int(i) for i in input().split()] for j in range(q)]
p = 10 ** 6 + 3

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(p - 1, p)
invf = invfact(p - 1, f, p)

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

    if x_over_d == 0 or x_over_d + n - 1 >= p:
        print(0)
        continue

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

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 1000003
q = int(input())
cumprod = [1]
for i in range(1, MOD):
	cumprod.append((cumprod[-1] * i) % MOD)

def calc(l, r):
	return (cumprod[r] * pow(cumprod[l-1], MOD-2, MOD)) % MOD

def solve(x, d, n):
	if x == 0:
		return 0
	elif d == 0:
		return pow(x, n, MOD)
	else:
		l = (x * pow(d, MOD-2, MOD)) % MOD
		if l+n-1 >= MOD:
			return 0
		else:
			return (calc(l, l+n-1) * pow(d, n, MOD)) % MOD

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

Submission status: Accepted

Solution code:
MOD = 1000003
q = int(input())
cumprod = [1]
for i in range(1, MOD):
	cumprod.append((cumprod[-1] * i) % MOD)

def calc(l, r):
	return (cumprod[r] * pow(cumprod[l-1], MOD-2, MOD)) % MOD

def solve(x, d, n):
	if x == 0:
		return 0
	elif d == 0:
		return pow(x, n, MOD)
	else:
		l = (x * pow(d, MOD-2, MOD)) % MOD
		if l+n-1 >= MOD:
			return 0
		else:
			return (calc(l, l+n-1) * pow(d, n, MOD)) % MOD

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

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

    if x == 0:
        ans.append(0)
        continue

    if d == 0:
        ans.append(pow(x, n, MOD))
        continue

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append(reduce(mod_mul, (fact[xd + n - 1], inv_fact[xd - 1], dn)))
print(*ans, sep='\n')
# 逐次printより,最後に一括が速いかどうか
# python3では
# reduce,mod_mulなしのans一括と
# 逐次printのreduce,mod_mulありが同速度だった
# pypyだと速くなった気がする

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3

fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

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

    if x == 0:
        ans.append(0)
        continue

    if d == 0:
        ans.append(pow(x, n, MOD))
        continue

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)
print(*ans, sep='\n')
# 逐次printより,最後に一括が速い？

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3

fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

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

    if x == 0:
        ans.append(0)
        continue

    if d == 0:
        ans.append(pow(x, n, MOD))
        continue

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3

fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

Q = int(input())
for _ 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 == 0:
        print(0)
        continue

    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = inv(fact[-1])
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

Q = int(input())
for _ 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 * inv(d)) % MOD
    if xd == 0:
        print(0)
        continue

    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = inv(fact[-1])
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

Q = int(input())
for _ 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 * inv(d)) % MOD
    if xd == 0:
        print(0)
        continue
        
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print((((fact[xd + n - 1] * inv_fact[xd - 1]) % MOD) * dn) % MOD)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = inv(fact[-1])
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ
    
Q = int(input())
for _ 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 * inv(d)) % MOD
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(reduce(mod_mul, (fact[xd + n - 1], inv_fact[xd - 1], dn)))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

Q = int(input())
for _ 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 * inv(d)) % MOD
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(reduce(mod_mul, (fact[xd + n - 1], inv(fact[xd - 1]), dn)))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def inv(n):
    return pow(n, MOD - 2, MOD)


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append(mod_mul(fact[-1], n))
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

Q = int(input())
for _ 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 = mod_mul(x, inv(d))
    if MOD - xd < n:
        print(0)
        continue

    dn = pow(d, n, MOD)
    print(mod_mul(mod_mul(fact[xd + n - 1], inv(fact[xd - 1])), dn))

Submission status: Accepted

Solution code:
mod = 10**6+3
max = 10**6+2
g1 = [1, 1]
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
def rev(a):
    return pow(a,mod-2,mod)
def f(x,d,n):
    if d==0:
        return pow(x,n,mod)
    else:
        d_r = rev(d)
        xdr = d_r * x % mod
        if xdr==0:
            return 0
        elif (xdr+n-1)>=mod:
            return 0
        else:
            return (g1[xdr+n-1]*rev(g1[xdr-1]%mod)*pow(d,n,mod))%mod
ans = []
q = int(input())
for _ in range(q):
    x,d,n = map(int,input().split())
    ans.append(f(x,d,n))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
MOD = 10**6+3
n = MOD + 10

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

q = int(input())

def f(x, d, n):
    if d == 0:
        return pow(x, n, MOD)
    p = (x * pow(d, MOD-2, MOD)) % MOD
    if p + n - 1 >= MOD:
        return 0
    q = fac[(p + n - 1) % MOD]
    r = fac[p - 1]
    s = pow(d, n, MOD)
    return (q*pow(r, MOD-2, MOD)*s) % MOD

for i in range(q):
    x, d, n = [int(item) for item in input().split()]
    print(f(x, d, n))

Submission status: Accepted

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]


Q = int(input())
items = []
for i in range(Q):
    items.append(tuple(map(int, input().split())))

mod = 10 ** 6 + 3
fact_mod = FactMod(mod - 1, mod)

for x, d, n in items:
    if d == 0:
        print(pow(x, n, mod))
    elif x == 0:
        print(0)
    else:
        # d の逆元
        invd = pow(d, mod - 2, mod)

        # x にd^-1をかける
        xd = x * invd % mod

        # 10**6が数列に存在しないか
        if n - 1 + xd >= mod:
            print(0)
            continue
        # 最後にd ** nをかける
        dn = pow(d, n, mod)
        print(fact_mod.fact(xd + n - 1) * fact_mod.inv[xd - 1] % mod * dn % mod)

Submission status: Accepted

Solution code:
p=1000003
def inv(x):
    return pow(x,p-2,p)
def exponen(a,b):
    return pow(a,b,p)
Fact=[0 for i in range(p)]
Fact[0]=1
for i in range(p-1):
    Fact[i+1]=((i+1)*Fact[i])%p
def fact(k):
    if 0<=k<p:
        return Fact[k]
    else:
        return 0
def solve(x,d,n):
    if x==0:
        return 0
    if d==0:
        return exponen(x,n)
    a=(x*inv(d))%p
    check=(-a)%p
    if 0<=check<=n-1:
        return 0
    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: Accepted

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, n, g))

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

Submission status: Accepted

Solution code:
Q = int(input())

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

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

Submission status: Accepted

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


Q = int(input())
items = []
for i in range(Q):
    items.append(tuple(map(int, input().split())))

mod = 10 ** 6 + 3
fact_mod = FactMod(mod - 1, mod)

for x, d, n in items:
    if d == 0:
        print(pow(x, n, mod))
    elif x == 0:
        print(0)
    else:
        invd = pow(d, mod - 2, mod)

        xd = x * invd % mod
        limit = mod - xd
        if n > limit:
            print(0)
            continue

        r = xd + n - 1
        l = xd - 1
        tmp = pow(d, n, mod)
        print(fact_mod.fact(r) * fact_mod.inv[l] * tmp % mod)

Submission status: Accepted

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
    anss = []
    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 > MOD or x == 0:
                ans = 0
            else:
                factor = pow(d, n, MOD)
                perm = fact[x + n - 1] * ifact[x - 1] % MOD
                ans = perm * factor % MOD
        anss.append(ans)
    print(*anss, sep='\n')
    return

main()

Submission status: Accepted

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 > MOD or x == 0:
                ans = 0
            else:
                factor = pow(d, n, MOD)
                perm = fact[x + n - 1] * ifact[x - 1] % MOD
                ans = perm * factor % MOD
        print(ans)
    return

main()

Submission status: Accepted

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

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

MOD = 1000003


def inv(x, m):
  y, u, v = m, 1, 0

  while y != 0:
    t = x // y
    x -= t * y
    u -= t * v
    x, y = y, x
    u, v = v, u

  return u % m


def main():
  facs = [None] * MOD
  invs = [None] * MOD

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

  invs[-1] = facs[-1]
  for i in range(MOD - 1, 0, -1):
    invs[i - 1] = invs[i] * i % MOD

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

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

    x = x * inv(d, MOD) % MOD

    if x + n - 1 >= MOD:
      print(0)
      continue

    v = facs[x + n - 1]

    if x != 0:
      v = v * invs[x - 1] % MOD

    if d != 1:
      v = v * pow(d, n, MOD) % MOD

    print(v)


if __name__ == '__main__':
  main()

Submission status: Accepted

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)
    t = pow(t, MOD - 2, MOD)
    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())

    if x == 0:
        ans.append(0)
        continue
    if d == 0:
        ans.append(pow(x, n, MOD))
        continue

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

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