Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from bisect import bisect_right

N,K=list(map(int, input().split()))
A=list(map(int, input().split()))
A.sort()
S=set(A)
S=list(S)
B=[]

def bisectsearch_right(L, a):
    i = bisect_right(L, a)
    return(i)

for i in S:
  a=A[0]
  j = bisect_right(A,a)
  B.append(j)
  A=A[j:]
B.sort()
# print(B)
C=B[:len(S)-K]
print(sum(C))


### FIXED CODE ###

from collections import Counter

N,K=list(map(int, input().split()))
A=list(map(int, input().split()))

dic = dict(Counter(A))
ls = list(dic.items())
ls.sort(key=lambda x: x[1])

i=0
ans=0
res=len(ls)
while 1:
  if res <= K or i >= N:
    break
  ans += ls[i][1]
  i+=1
  res-=1
print(ans)
### BUGGY CODE ###

import bisect

D = 10 ** 6

X = int(input())

L = [i**5 for i in range(-D, D)]
L2 = [i for i in range(-D, D)]

idx = bisect.bisect_left(L, X)-1

B = L[:idx]
A = L[idx:]

for a in A:
    for b in B:
        if a - b == X:
            break
    else:
        continue
    break

print(L2[L.index(a)], L2[L.index(b)])


### FIXED CODE ###

import bisect
import math

D = 120

X = int(input())

for a in range(-D, D):
    for b in range(-D-1, D-1):
        if a**5 - b**5 == X:
            break
    else:
        continue
    break

print(a, b)
### BUGGY CODE ###

N = int(input())
A = []
c = 0
for n in input().split():
  i = int(n)
  A.append(i)
for i in range(N):
  Ai = A[i]
  flg = True
  for j in range(N):
    if i == j:
      continue
    Aj = A[j]
    if Ai % Aj == 0:
      flg = False
      break
  if flg:
    c += 1
print(c)
    
    

### FIXED CODE ###

N = int(input())
c=[0]*8**7
for a in input().split():
    c[int(a)] += 1
i=r=0
for t in c:
    if t:
        c[::i]=[0]*-(-8**7//i)
    i+=1
    r+=t==1
print(r)
### BUGGY CODE ###

N, W = map(int, input().split())
X = [0] + [-1] * W

for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(W - w, -1, -1):
        if X[j] >= 0:
            X[j+w] = max(X[j+w], X[j]+v)

print(max(X))

### FIXED CODE ###

N, W = map(int, input().split())
X = [0] + [-1] * W

for i in range(N):
    w, v = map(int, input().split())
    
    for j in range(W - w, -1, -1):
        if X[j] >= 0:
            X[j+w] = max(X[j+w], X[j]+v)

print(max(X))
### BUGGY CODE ###

import numba
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])
@numba.njit("void(i8,i8[:])")
def proc(N, P):
    ans = 0
    Removed = np.zeros((N, N), dtype=np.int8)
    Mat = np.zeros((N, N), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y][x]
        #print(p, Mat[y][x])
        Removed[y][x] = 1
        #Mat[y][x] -= 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy][vx]
            val = Mat[vy][vx]
            for dy, dx in zip(Dy, Dx):
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy][ux]
                if vr:
                    if Mat[uy][ux] >= val+1:
                        Mat[uy][ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy][ux] >= val+2:
                        Mat[uy][ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)



### FIXED CODE ###

import numba
import numpy as np
N = int(input())
P = np.array([int(c)-1 for c in input().split()])

#from random import shuffle
#N = 500
#P = list(range(N*N))
#shuffle(P)
#P = np.array(P)

@numba.njit("void(i8,i8[:])")
def proc(N, P):
    ans = 0
    Removed = np.zeros((500, 500), dtype=np.int8)
    Mat = np.zeros((500, 500), dtype=np.int16)
    Dy, Dx = [1,0,-1,0], [0,1,0,-1]

    for y in range(N):
        for x in range(N):
            Mat[y, x] = min(y, N-1-y, x, N-1-x)
    #print(Mat)
    for i in range(N*N):
        p = P[i]
        y, x = divmod(p, N)
        ans += Mat[y,x]
        Removed[y,x] = 1
        st = [(y, x)]
        while st:
            vy, vx = st.pop()
            vr = Removed[vy,vx]
            val = Mat[vy,vx]
            #for dy, dx in zip(Dy, Dx):
            for j in range(4):
                dy = Dy[j]
                dx = Dx[j]
                uy = vy + dy
                ux = vx + dx
                if not (0<=uy<N and 0<=ux<N):
                    continue
                ur = Removed[uy,ux]
                if vr:
                    if Mat[uy,ux] >= val+1:
                        Mat[uy,ux] = val
                        st.append((uy, ux))
                else:
                    if Mat[uy,ux] >= val+2:
                        Mat[uy,ux] = val+1
                        st.append((uy, ux))
    # for m in Mat:
    #     print(m)
    print(ans)
proc(N, P)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = [int(a) * (-1) for a in input().split()]

for _ in range(M):
    B, C = map(int, input().split())
    tmp = [C * (-1)] * B
    A.extend(tmp)

heapq.heapify(A)

ans = 0
for _ in range(N):
    ans += heapq.heappop(A)

print(ans * (-1))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [int(a) * (-1) for a in input().split()]

B_array = []
for _ in range(M):
    B, C = map(int, input().split())
    B_array.append([C * (-1), B])
B_array.sort()

cnt = 0
i = 0
B_list = []
while cnt < N and i < M:
    B_list.extend([B_array[i][0]] * B_array[i][1])
    cnt += B_array[i][1]
    i += 1

A.extend(B_list)
heapq.heapify(A)

ans = 0
for _ in range(N):
    ans += heapq.heappop(A)
        
print(ans * (-1))
### BUGGY CODE ###

H = int(input())

cnt = H
B = [H]

for i in range(100000000000):
    cnt = cnt//2
    B.append(cnt)
    if cnt == 1:
        break

C =[1]
for i in range(1,1001):
    C.append(C[i-1]*2)

#print(len(C))
ans= 0
for i in range(len(B)):
    ans +=C[i]

if H == 1:
    print('0')
else:
    print(ans)

### FIXED CODE ###

H = int(input())
cnt = H
ans = 0
B = [H]

if H == 1:
    ans == 'NA'
else:
    for i in range(100000000000):
        cnt = cnt//2
        B.append(cnt)
        if cnt == 1:
            break

C =[1]
for i in range(1,1001):
    C.append(C[i-1]*2)

if ans == 'NA':
    print('0')
else:
    for i in range(len(B)):
        ans +=C[i]
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
N=[0]*2020
x=0
for i in reversed(range(n)):
    x+=int(s[i])*(10**(n-i-1))
    N[x%2019]+=1
ans=s.count('0')
ans+=N[0]
for j in N:
    ans+=j*(j-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
s=input()
n=len(s)
N=defaultdict(int)
x=0
for i in reversed(range(n)):
    x+=int(s[i])*pow(10,(n-i-1),2019)
    x%=2019
    N[x]+=1
ans=N[0]
for j in N.values():
    ans+=j*(j-1)//2
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


def solve(N, K, data):
    WHITE, GRAY, BLACK = 0, 1, 2

    num_of_nodes = N+1
    color = [WHITE] * num_of_nodes  # 各ノードの訪問状態
    d = [float('inf')] * num_of_nodes  # 始点からの重み
    adj = [[] for _ in range(num_of_nodes)]

    for f, t, c in data:
        adj[f].insert(0, (t, c))
        adj[t].insert(0, (f, c))


    # dijkstra(self, start):
    d[K] = 0
    pq = [(0, K)]

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, c in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heappush(pq, (d[v], v))
                color[v] = GRAY
    return d



def main():
    # データの入力
    N = int(input())
    data = []
    for i in range(N-1):
        data.append(list(map(int, input().split(' '))))
    queries = []
    Q, K = [int(x) for x in input().split(' ')]
    for i in range(Q):
        queries.append([int(x) for x in input().split(' ')])

    # 経路の探索
    d = solve(N, K, data)

    # 結果の表示
    for q in queries:
        print(d[q[0]] + d[q[1]])


if __name__ == '__main__':
    main()
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://abc070.contest.atcoder.jp/tasks/abc070_d
"""
# TLEするので、ダイクストラのアルゴリズムからの高速化が必要。
# 隣接行列をやめて隣接リストにしたところ、だいぶ速度が改善された。しかし、今度はWAが出るようになった。
# WAはコスト無限大の設定値が低すぎたため、経路コストがオーバーしてしまっていたため。float('inf')にして TLEのみになった
# d[]をnumpyの行列にしてみた → 遅くなっただけ
# クラスをやめてベタ書きに
from heapq import heappush, heappop


# データの入力
N = int(input())
adj = [[] for _ in range(N+1)]
for i in range(N-1):
    f, t, c = [int(x) for x in input().split(' ')]
    adj[f].append((t, c))
    adj[t].append((f, c))

queries = []
Q, K = [int(x) for x in input().split(' ')]
for _ in range(Q):
    queries.append([int(x) for x in input().split(' ')])

# 経路の探索
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * (N+1)  # 各ノードの訪問状態
d = [float('inf')] * (N+1)  # 始点からの重み

# dijkstra
d[K] = 0
pq = [(0, K)]

while pq:
    cost, u = heappop(pq)
    color[u] = BLACK
    if d[u] < cost:
        continue

    for v, c in adj[u]:
        if color[v] == BLACK:
            continue
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            color[v] = GRAY

# 結果の表示
for x, y in queries:
    print(d[x] + d[y])
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ls = [0] * n
    mt = [0] * n
    cnt = 0
    for w in range(10 ** 15):
        cnt += 1
        f = [False] * n
        for i in range(n):
            if ls[i] != -1:
                mt[i] = a[i][ls[i]]
        bb = False
        for i in range(n):
            if not f[i]:
                if ls[i] != -1:
                    if i + 1 == mt[mt[i]-1]:
                        if ls[i] + 1 < n - 1:
                            ls[i] += 1
                            bb = True
                        else:
                            ls[i] = -1
        b = True
        for i in range(n):
            if ls[i] != -1:
                b = False
                break
        if b:
            print(cnt)
            exit()
        if not bb:
            print(-1)
            exit()


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


if __name__ == '__main__':
    slove()
### BUGGY CODE ###

n = int(input())
i = 2
ans = n - 1
while i < n:
  if i * i > n:
    break
  if n % i > 0:
    continue
  j = n // i
  ans = min(ans, i + j - 2)
  i += 1
print(ans)

### FIXED CODE ###

n = int(input())
i = 2
ans = n - 1
while i < n:
  if i * i > n:
    i += 1
    break
  if n % i > 0:
    i += 1
    continue
  j = n // i
  ans = min(ans, i + j - 2)
  i += 1
print(ans)
### BUGGY CODE ###

from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n = int(input())
l = [int(x) for x in input().split()]

ll = [x for x in set(l) if l.count(x) > 1]

sm = 0
m = [1 for x in range(n)]
for i in ll:
    t = l.count(i)
    sm += combinations_count(t, 2)
    m[i-1] = t

for i in l:
    print(sm-(m[i-1]-1))


### FIXED CODE ###

import collections

def combinations_count(n, r):
    return n * (n-1) // r


n = int(input())
l = [int(x) for x in input().split()]

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    print(total-combinations_count(c[a], 2)+combinations_count(c[a]-1, 2))
### BUGGY CODE ###

X,K,D = map(int,input().split())

if X>0:
    p = True
else:
    p = False
c = 0
while abs(X)> D:
    if p :
        X -= D
        K -= 1
    else:
        X += D
        K -= 1
    if K == 0:
        break

if K > 0:
    if K%2 == 1 and p == True:
        X = X - D
    if K%2 == 1 and p == False:
        X = X + D

print(abs(X))

### FIXED CODE ###

X,K,D = map(int,input().split())
A = abs(X)
ans = 0
if A >= D*K:
    print( A - (D * K))
else :
    e = A//D
    K -= e
    A %= D
    if K%2 == 0:
        print(A)
    else:
        print(D-A)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
c = 0
for r in range(0, N+1):
  for g in range(0, N+1):
    n = N-r*R-g*G
    if n < 0:
      continue
    if n%B == 0:
      c += 1
print(c)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
R, G, B = sorted([R, G, B], reverse=True)
if B == 1:
  c = 0
  for r in range(0, N+1):
    if r*R > N:
      break
    n = N-r*R
    c += 1+n//G
  print(c)
  exit()
c = 0
for r in range(0, N+1):
  if r*R > N:
    break
  for g in range(0, N+1):
    if r*R+g*G > N:
      break
    n = N-r*R-g*G
    if n%B == 0:
      c += 1
print(c)
### BUGGY CODE ###

def do():
    n=int(input())
    l=list(map(int,input().split()))
    k=1
    for i in l:
        k*=i
    if k > 1 * 10 ** 18:
        return -1
    return k
print(do())



### FIXED CODE ###

def do():
    n=int(input())
    l=list(map(int,input().split()))
    k=1
    if 0 in l:
        return 0
    for i in l:
        k*=i
        if k>1*10**18:
            return -1
    return k
print(do())
### BUGGY CODE ###

from collections import deque

n = int(input())
neibors = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map( int, input().split() )
    neibors[u-1].append( (v-1,w%2) )
    neibors[v-1].append( (u-1,w%2) )

dist = [0 for i in range(n)]
stack = deque([0])
used = [0]
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if neibor_n not in used:
            used.append( neibor_n )
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)

### FIXED CODE ###

from collections import deque

n = int(input())
neibors = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map( int, input().split() )
    neibors[u-1].append( (v-1,w%2) )
    neibors[v-1].append( (u-1,w%2) )

dist = [-1 for i in range(n)]
stack = deque([0])
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if dist[neibor_n] == -1:
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)
### BUGGY CODE ###

s = str(input())
mod = 2019
li = [int(s[-1])]
for i in range(len(s) - 1):
    li.append((li[-1] + int(s[-(2 + i)]) * (10 ** (i + 1))) % mod)
import collections
A=collections.Counter(li)
ans=0
for u,v in A.items():
    ans+=v*(v-1)//2
    if u==0:
        ans+=v
print(ans)




### FIXED CODE ###

s = str(input())
s=s[::-1]
mod = 2019
li = [0]*(len(s)+1)
cnt=1
for i in range(len(s)):
    li[i+1]=li[i] + int(s[i]) * cnt
    li[i+1]%=mod
    cnt*=10
    cnt%=mod
import collections
A=collections.Counter(li[1:]);ans=0
for u,v in A.items():
    ans+=v*(v-1)//2
    if u==0:
        ans+=v
print(ans)
### BUGGY CODE ###

# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

N = int(input())
A = list(map(int, input().split()))

ans = [0 for _ in range(N)]

ans_num = 0
ans_list = ""
for i in range(N):
    tmp = N - i
    s = 0
    for j in range(tmp, N+1, tmp):
        s += ans[j-1]

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1
        ans_num += 1
        ans_list += str(tmp)
        ans_list += " "


print(ans_num)
print(ans_list[:-1])

### FIXED CODE ###

# 1からNまでの数字それぞれの約数を求める
# Nから(大きい値から)見ていき、1であれば入れる
# 数字iを入れた場合、iの約数の数を+1
# それぞれの数はdictで保持する

N = int(input())
A = list(map(int, input().split()))

ans = [0 for _ in range(N)]

ans_num = 0
ans_list = ""
for i in range(N):
    tmp = N - i
    s = 0
    for j in range(tmp, N+1, tmp):
        s += ans[j-1]

    if s % 2 != A[tmp - 1]:
        ans[tmp - 1] = 1
        ans_num += 1
        ans_list += str(tmp)
        ans_list += " "


print(ans_num)
print(ans_list[:-1])
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split()))+[0] for _ in range(H)]
B = [list(map(int, input().split()))+[0] for _ in range(H)]
A.append([0]*(W+1))
B.append([0]*(W+1))


dp = [[set([]) for _ in range(W+2)] for _ in range(H+2)]
diff = A[0][0] - B[0][0]
dp[0][0].add(diff)
dp[0][0].add(-diff)

# 配るDP
for h in range(H):
    for w in range(W):
        dif_r = abs(A[h + 1][w] - B[h + 1][w])
        dif_d = abs(A[h][w + 1] - B[h][w + 1])
        for val in dp[h][w]:
            if val + dif_r <= 80:
                dp[h+1][w].add(val+dif_r)
            if val - dif_r <= 80:
                dp[h+1][w].add(val-dif_r)
            if val + dif_d <= 80:
                dp[h][w+1].add(val+dif_d)
            if val - dif_d <= 80:
                dp[h][w+1].add(val-dif_d)

ans = 10 ** 9
for val in dp[H-1][W-1]:
    ans = min(ans, abs(val))

print(ans)


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
A = np.array([input().split() for _ in range(H)], dtype=int)
B = np.array([input().split() for _ in range(H)], dtype=int)
dif = np.abs(A - B).tolist()

U = (H + W) * 80
Um = U // 2

dp = [[[] for _ in range(W)] for _ in range(H)]
X = np.zeros(U + 1, dtype=bool)
X[Um + dif[0][0]] = True
X[Um - dif[0][0]] = True
dp[0][0] = X


for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        d = dif[i][j]
        X = np.zeros(U + 1, dtype=bool)
        if d:
            if i > 0:
                X[d:] |= dp[i - 1][j][:-d]
                X[:-d] |= dp[i - 1][j][d:]
            if j > 0:
                X[d:] |= dp[i][j - 1][:-d]
                X[:-d] |= dp[i][j - 1][d:]
        else:
            if i > 0:
                X |= dp[i - 1][j]
            if j > 0:
                X |= dp[i][j - 1]
        dp[i][j] = X

tmp = np.arange(U+1)[dp[H-1][W-1]]
ans = np.abs(tmp - Um).min()
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

cs_a, cnt = [0] * n, 0
for i in range(n):
    cnt += a[i]
    cs_a[i] = cnt
dp = [[0] * (k + 1) for i in range(n + 1)]

for i in range(n + 1):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        elif (i == 0) or (j > cs_a[i - 1]):
            dp[i][j] = 0
        elif j - a[i - 1] - 1 < 0:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - a[i - 1] - 1]

print(dp[n][k] % (10 ** 9 + 7))


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

cs_a, cnt = [0] * n, 0
for i in range(n):
    cnt += a[i]
    cs_a[i] = cnt
dp = [[0] * (k + 1) for i in range(n + 1)]

for i in range(n + 1):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        elif (i == 0) or (j > cs_a[i - 1]):
            dp[i][j] = 0
        elif j == 1:
            dp[i][j] = dp[i - 1][j] + min(a[i - 1], 1)
        elif j - a[i - 1] - 1 < 0:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - a[i - 1] - 1]
        dp[i][j] %= 10 ** 9 + 7

print(dp[n][k])
### BUGGY 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)


### FIXED 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)
### BUGGY CODE ###

import math
from functools import reduce
n = int(input())


sum = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            tmp = math.gcd(i,j)
            tmp2 = math.gcd(j,k)
            tmp3 = math.gcd(tmp,tmp2)
            sum += tmp3
print(sum)

### FIXED CODE ###

import math
from functools import reduce
n = int(input())
 
 
sum = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            tmp = math.gcd(i,j)
            tmp2 = math.gcd(j,k)
            tmp3 = math.gcd(tmp,tmp2)
            sum += tmp3
print(sum)
### BUGGY CODE ###

n = int(input())
P = list(map(int, input().split()))
c = 0
for i in range(n):
  if i ==0: 
    c+=1
  elif P[i] < min(P[0:i]): 
    c +=1
print(c)

### FIXED CODE ###

n = int(input())
P = list(map(int, input().split()))
c = 0
for i in range(n):
  if i ==0: 
    c+=1
    current_min = P[i]
  elif P[i] < current_min: 
    c +=1
    current_min = P[i]
print(c)