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:
# 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 = [1]
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l.append(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: 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: Time Limit Exceeded

Solution code:
from itertools import accumulate
from operator import mul

# 入力
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 = [ModInt(1)] + list(
    accumulate(
        map(ModInt, range(1, MOD)),
        mul
    )
)


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

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

p=1000003

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

  cnt=0
  data1=1
  for i in range(p-2):
    cnt+=1
    data1*=d
    data1=data1%p
  data2=(x*data1)%p

  data3=1
  for i in range(n):
    data3*=(data2+i)
    data3=data3%p
  
  for i in range(n):
    data3*=d
    data3=data3%p
    
  print(data3)

Submission status: Time Limit Exceeded

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]

ans = '\n'.join(
    str(
        X**N if D == 0 else
        D**N * f[(X / D).x + N - 1] / f[(X / D).x - 1] if (X / D).x + N - 1 < MOD else
        0
    )
    for X, D, N in zip(map(ModInt, x), d, n)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

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, self.pow(b, self.m-2))

    # @lru_cache(maxsize=None)
    def pow(self, x, y):
        if y == 0:
            return 1
        elif y == 1:
            return x % self.m
        elif y % 2 == 0:
            return self.pow(x, y//2)**2 % self.m
        else:
            return self.pow(x, y//2)**2 * x % 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()
    # ans = []
    for _ in range(Q):
        x, d, n = read_int_n()
        print(slv(x, d, n))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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, self.pow(b, self.m-2))

    @lru_cache(maxsize=None)
    def pow(self, x, y):
        if y == 0:
            return 1
        elif y == 1:
            return x % self.m
        elif y % 2 == 0:
            return self.pow(x, y//2)**2 % self.m
        else:
            return self.pow(x, y//2)**2 * x % self.m


M = 1000003
m = Mod(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


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()
    ans = []
    for _ in range(Q):
        x, d, n = read_int_n()
        ans.append(slv(x, d, n))
    print('\n'.join(map(str, ans)))

    # ans = []
    # print(10**5)
    # for _ in range(10**5):
    #     x = random.randint(0, M-1)
    #     d = random.randint(0, M-1)
    #     n = random.randint(1, 10**9)
    #     print(x, d, n)
    #     ans.append(slv(x, d, n))
    # # print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod=1000003

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

#def power(x, y):
#    if   y == 0     : return 1
#    elif y == 1     : return x % mod
#    elif y % 2 == 0 : return power(x, y//2)**2 % mod
#    else            : return power(x, y//2)**2 * x % mod
def power(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % mod
        x *= x % mod
        n //= 2

    return K * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

for j in range(q):
    x,d,n=(int(i) for i in input().split())  
    xd=div(x, d)
    ans=1
    if mod <= xd+n-1:
        ans=0

    for i in range(n):
        ans=mul(ans,xd+i)
    
    print((power(d,n)*ans)%mod)

Submission status: Time Limit Exceeded

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

mod=1000003

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

#def power(x, y):
#    if   y == 0     : return 1
#    elif y == 1     : return x % mod
#    elif y % 2 == 0 : return power(x, y//2)**2 % mod
#    else            : return power(x, y//2)**2 * x % mod
def power(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x

def div(a, b):
    return mul(a, power(b, mod-2))

for j in range(q):
    x,d,n=(int(i) for i in input().split())  
    xd=div(x, d)
    ans=1
    if mod <= xd+n-1:
        ans=0

    for i in range(n):
        ans=mul(ans,xd+i)
    
    print((power(d,n)*ans)%mod)

Submission status: Time Limit Exceeded

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

mod=1000003

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

for j in range(q):
    x,d,n=(int(i) for i in input().split())  
    xd=div(x, d)
    ans=1
    if mod <= xd+n-1:
        ans=0

    for i in range(n):
        ans=mul(ans,xd+i)
    
    print((power(d,n)*ans)%mod)

Submission status: Time Limit Exceeded

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

mod=1000003

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

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

  ans=1
  for i in range(n):
    ans=mul(ans,xd+i)
    
  print((power(d,n)*ans)%mod)

Submission status: Time Limit Exceeded

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 list(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, self.pow(b, self.m-2))

    @lru_cache(maxsize=None)
    def pow(self, x, y):
        if y == 0:
            return 1
        elif y == 1:
            return x % self.m
        elif y % 2 == 0:
            return self.pow(x, y//2)**2 % self.m
        else:
            return self.pow(x, y//2)**2 * x % self.m


M = 1000003
m = Mod(M)

f = [1]
for i in range(1, M):
    f.append(m.mul(f[-1], i))


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.div(f[xd+n-1], f[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: Time Limit Exceeded

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)

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

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
finv = [pow(f, MOD-2, MOD) for f in fact]

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

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

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

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

Solution code:
t= int(input())
for i in range(t):
  a,d,n = list(map(int,input().split()))
  # arr = np.linspace(a,a+(n-1)*d,n).astype("int")
  #arr=arr%mod
  prod = 1
  mod=1000003
  for i in range(n):
      prod=prod*(a%mod)
      prod=prod%mod
      a+=d
  print(prod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

g = 1000003
for x, d, n in (map(int, input().split()) for _ in range(N)):
    ans = 1

    for _ in range(n):
        ans = ans * x % g
        x += d

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**6 + 3

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

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

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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**6 + 3

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

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

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

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

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


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

Submission status: Time Limit Exceeded

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

MOD = 1000003


class ModInt(object):

  def __init__(self, num, mod):
    self.num = num
    self.mod = mod

    if self.num >= self.mod:
      self.num %= self.mod

  def inv(self):
    a, b, u, v = self.mod, self.num, 0, 1

    while b != 0:
      t = a // b
      a -= t * b
      u -= t * v
      a, b = b, a
      u, v = v, u

    return ModInt(u % self.mod, self.mod)

  def __add__(self, n):
    raise NotImplementedError()

  def __sub__(self, n):
    raise NotImplementedError()

  def __mul__(self, n):
    return ModInt((self.num * int(n)) % self.mod, self.mod)

  def __div__(self, n):
    raise NotImplementedError()

  def __pow__(self, n):
    v = 1
    m = self.num

    while n != 0:
      if n & 1 != 0:
        v = (v * m) % self.mod

      m = (m * m) % self.mod
      n = n >> 1

    return ModInt(v, self.mod)

  def __int__(self):
    return self.num

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


def main():
  facs = [None] * MOD
  facs[0] = ModInt(1, MOD)

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

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

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

    x = int(ModInt(x, MOD) * ModInt(d, MOD).inv())

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

    v = facs[x + n - 1]

    if x != 0:
      v *= facs[x - 1].inv()

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

    print(v)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**6 + 3

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

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

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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
def calc(x, d, n):
  Answer = 1
  for i in range(n):
    Answer = Answer * (x + i*d)
  return Answer

for s in range(N):
  x, d, n = map(int, input().split())
  print(calc(x, d, n) % 1000003)