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:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 6 + 3
modpow = lambda a, n, p = MOD: pow(a, n, p)
# Recursive function in python is slow!
# def modpow(a, n, p = MOD):
#     if   n == 0     : return 1
#     elif n == 1     : return a % p
#     elif n % 2 == 0 : return modpow(a, n//2, p)**2 % p
#     else            : return modpow(a, n//2, p)**2 * a % p
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

input2 = lambda: sys.stdin.readline().strip()
r = sys.stdin.readline #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]

# calculate
fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Accepted

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 6 + 3
modpow = lambda a, n, p = MOD: pow(a, n, p)
# Recursive function in python is slow!
# def modpow(a, n, p = MOD):
#     if   n == 0     : return 1
#     elif n == 1     : return a % p
#     elif n % 2 == 0 : return modpow(a, n//2, p)**2 % p
#     else            : return modpow(a, n//2, p)**2 * a % p
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

input2 = sys.stdin.readline
r = sys.stdin.readline #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]

# calculate
fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

q = int(input())
mod = 10**6+3
f = {}
f[0] = 1
for i in range(1,mod):
	f[i] = f[i-1] * i % mod

for i in range(q):
	x,d,n = m()
	if d == 0:
		ans = pow(x,n,mod)
	else:
		x = x * pow(d,mod-2,mod)%mod
		if mod <= x + n - 1:
			ans = 0
		else:
			ans = pow(d,n,mod) * f[x+n-1] * pow(f[x-1],mod-2,mod) % mod
	print(ans)

Submission status: Accepted

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def modpow(a, n, p = MOD):
    if   n == 0     : return 1
    elif n == 1     : return a % p
    elif n % 2 == 0 : return modpow(a, n//2, p)**2 % p
    else            : return modpow(a, n//2, p)**2 * a % p
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

input2 = sys.stdin.readline
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]

# calculate
fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n, MOD))
    else:
        x = moddiv(x, d, MOD)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1], MOD),modpow(d, n, MOD), MOD))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Accepted

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list!
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 6 + 3
def modpow(a, n, p = MOD):
    if   n == 0     : return 1
    elif n == 1     : return a % p
    elif n % 2 == 0 : return modpow(a, n//2, p)**2 % p
    else            : return modpow(a, n//2, p)**2 * a % p
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# q = 2
# xdn = [[7, 2, 4], [12345, 67890, 2019]]

input2 = sys.stdin.readline
R = lambda: list(map(int, input2().split()))
q = int(input())
xdn = [R() for _ in range(q)]

# calculate
fac_list = modfactorial_list(MOD)
for x, d, n in xdn:
    if d == 0:
        print(modpow(x, n))
    else:
        x = moddiv(x, d)
        if x + n - 1 >= MOD:
            print(0)
        else:
            print(modmul(moddiv(fac_list[x+n-1], fac_list[x-1]),modpow(d, n)))
# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6

Submission status: Accepted

Solution code:
Q = int(input())
xdn = [[int(i) for i in input().split()] for _ in range(Q)]

MOD = 10 ** 6 + 3

fact = [0] * MOD
inv = [0] * MOD
fact[0] = 1
inv[0] = pow(fact[0], MOD - 2, MOD)

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

for x, d, n in xdn :
    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((fact[xd + n - 1] * inv[xd - 1] * pow(d, n, MOD)) % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
q = int(input())

p=1000003

fdict={}
fdict[0]=1
for i in range(1,p):
    fdict[i]=fdict[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*fdict[x+n-1]*pow(fdict[x-1],p-2,p)%p
  print(ans%p)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
q = int(input())

p=1000003

flist=[1 for i in range(p)]
for i in range(1,p):
    flist[i]=flist[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)

Submission status: Accepted

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

MUL=[1]
for i in range(1,mod):
    MUL.append(MUL[-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
    start=x*pow(d,mod-2,mod)%mod
    if start+n-1>=mod:
        print(0)
    else:
        print(MUL[start+n-1]*pow(MUL[start-1],mod-2,mod)%mod*pow(d,n,mod)%mod)

Submission status: Accepted

Solution code:
# 入力
Q = int(input())
x, d, n = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), (), ())
)

MOD = 1000003


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# MOD未満の整数について、階乗を求めておく
# 各クエリに対して、d^n * (x/d + (n - 1))! / ((x/d) - 1)! を回答する
f = [0 for _ in range(MOD)]
f[0] = ModInt(1)
for i in range(1, MOD):
    f[i] = i * f[i - 1]


def q(X, D, N):
    Y = (
        0 if D.x == 0 else
        X / D
    )
    return (
        X**N if D.x == 0 else
        D**N * f[Y.x + N - 1] / f[Y.x - 1] if Y.x + N - 1 < MOD else
        0
    )


ans = '\n'.join(
    str(q(X, D, N))
    for X, D, N in zip(map(ModInt, x), map(ModInt, d), n)
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return map(int, input().split())


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


M = 1000003
m = Mod(M)
C = Combination(M-1, M)


def slv(x, d, n):
    if d == 0:
        return m.pow(x, n)

    xd = m.div(x, d)
    if n > M - xd:
        return 0

    return m.mul(m.mul(C.g1[xd+n-1], C.g2[xd-1]), m.pow(d, n))


def main():
    Q = read_int()
    for _ in range(Q):
        x, d, n = read_int_n()
        print(slv(x, d, n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
M=10**6+3
Q=int(input())
xdn=list(list(map(int,input().split())) for _ in range(Q))
factorial_list=[1]
for i in range(1,M):
    factorial_list.append(factorial_list[i-1]*i%M)
for x,d,n in xdn:
    t=x*pow(d,M-2,M)%M
    if d==0:
        print(pow(x,n,M))
    elif t+n<=M:
        print(factorial_list[t+n-1]
              *pow(factorial_list[t-1],M-2,M)
              *pow(d,n,M)%M)
    else:
        print(0)

Submission status: Accepted

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

def inpl(): return list(map(int, input().split()))
Q = int(input())
 
MOD = 10**6 + 3
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
size = MOD + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル

for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

for _ in range(Q):
    x, d, n = inpl()
    xd = x*inverse[d]%MOD
    if d != 0:
        if n < ((MOD-x)*inverse[d] + 1)%MOD:
            n = n%MOD
            print((g1[(xd + n - 1)%MOD] * g2[(xd-1)%MOD] * pow(d, n, MOD))%MOD)
        else:
            print(0)
    else:
        print(pow(x, n, MOD))

Submission status: Accepted

Solution code:
class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L
  def invN(s, n):
    L = [0, 1]
    for i in range(2, n):
      L.append(s.MOD - L[s.MOD % i] * (s.MOD // i) % s.MOD)
    return L

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

MOD = 1000003
inv = Inv(MOD)

L = [1] * MOD
IL = [1] * MOD
for i in range(1, MOD):
  L[i] = L[i - 1] * i % MOD
  IL[i] = inv.invx(L[i])

for x, d, n in xdn:
  if d == 0:
    print(inv.modpow(x, n))
    continue

  id = inv.invx(d)
  k = x * id % MOD
  if k + n > MOD:
    print(0)
    continue
  t = inv.modpow(d, n)
  print(L[k + n - 1] * IL[k - 1] * t % MOD)

Submission status: Accepted

Solution code:
MOD = 1000003
MAX = MOD
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0:
    return 0
  return (((fact[n]*invfact[k])%MOD)*invfact[n-k])%MOD

comb_build(MAX)

q = int(input())
for i in range(q):
  x, d, n = list(map(int, input().split()))
  if x==0 or d==0:
    print(pow(x, n, MOD))
    continue

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

Submission status: Accepted

Solution code:
p,M=pow,1000003
f=[1]*M
for i in range(1,M):f[i]=f[i-1]*i%M
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print[p(x,n,M),M/(t+n)and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0]

Submission status: Accepted

Solution code:
p,M=pow,1000003
f=[1]*M
for i in range(1,M):f[i]=f[i-1]*i%M
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print[p(x,n,M),M/(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0]

Submission status: Accepted

Solution code:
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print[p(x,n,M),M/(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0]

Submission status: Accepted

Solution code:
p,M,f=pow,1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*input():x,d,n=map(int,raw_input().split());t=x*p(d,M-2,M)%M;print([p(x,n,M),M/(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Submission status: Accepted

Solution code:
p,M,f=pow,1000003,[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*p(d,M-2,M)%M;print([p(x,n,M),M//(t+n)*t and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Submission status: Accepted

Solution code:
p,M,f=pow,1000003,[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*p(d,M-2,M)%M;print([p(x,n,M),(M-n>=t>0)*1and f[t+n-1]*p(f[t-1],M-2,M)*p(d,n,M)%M][d>0])

Submission status: Accepted

Solution code:
M,f=1000003,[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;print([pow(x,n,M),(M-n>=t>0)*1and f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M][d>0])

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
	print([pow(x,n,M),(M-n>=t>0)*1and f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M][d>0])

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 0<t<=M-n:
		print(f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M)
	else:
		print(0)