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

import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))


### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

mod = 998244353

N, S, *A = map(int, open(0).read().split())

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod

        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= mod

print(dp[N][S])

### FIXED CODE ###

mod = 998244353

N, S, *A = map(int, open(0).read().split())

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i, a in enumerate(A):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod

        if j + a <= S:
            dp[i + 1][j + a] += dp[i][j]
            dp[i + 1][j + a] %= mod

print(dp[N][S])
### BUGGY CODE ###

x = int(input())
n = 10**7

def blp(dp,num):
    l = 0
    r = len(dp)-1
    while l <= r:
        mid = (l+r)//2
        if num == dp[mid]:return mid
        elif num >= dp[mid]:l = mid+1
        else:r = mid-1
    return 0

def bln(dp,num):
    l = 0
    r = len(dp)-1
    while l>=r:
        mid = (l+r)//2
        if num == dp[mid]:return mid
        elif num >= dp[mid]:r = mid+1
        else:l = mid-1
    return 0
            
ap = [i**5 for i in range(n)]
an = [-(i**5) for i in range(n)]

for b in range(-n,n):
    num = x + b**5
    a = max(blp(ap,num),bln(an,num))
    if a:print(a,b) ; break

### FIXED CODE ###

x = int(input())
n = 100000
 
def binp(arr, val):
    left,right = 0,len(arr)-1
    while left <= right:
        mid = (left+right)//2
        if val==arr[mid]: return mid
        elif val>=arr[mid]: left = mid+1
        else: right = mid-1
    return 0
 
def binn(arr, val):
    left,right = 0,len(arr)-1
    while left >= right:
        mid = (left+right)//2
        if val==arr[mid]: return mid
        elif val>=arr[mid]: right = mid+1
        else: left = mid-1
    return 0
 
ap = [i**5 for i in range(n)]
an = [-(i**5) for i in range(n)]
 
for b in range(-n,n):
    val = x + b**5
    a = max(binp(ap, val), binn(an,val))
    if a: print(a,b) ; break
### BUGGY CODE ###

N, M = list(map(int, input().split()))
As = list(map(int, input().split()))
Bs = []
Cs = []
cards = {}
for i in range(N):
    cards[As[i]] = cards.get(As[i], 0) + 1

for i in range(M):
    b, c = list(map(int, input().split()))
    Bs.append(b)
    Cs.append(c)
    cnt = 0
    for k in sorted(filter(lambda x: x < c, cards.keys())):
        for _ in range(cards.get(k,0)):
            cards[k] = cards[k] - 1
            if cards[k] == 0:
                del(cards[k])
            cards[c] = cards.get(c, 0) + 1
            cnt += 1
            # print('aaa:   ', b, c, cnt)
            if cnt >= b:
                break
        if cnt >= b:
            break
    # print()
    # print(cards)
    # print()

# print(list(cards.items()))
print(sum([k * cnt for k,cnt in cards.items()]))




### FIXED CODE ###

N, M  = map(int,input().split())
As = sorted(list(map(int,input().split())))
di = {}
for i in range(M):
    b, c = map(int,input().split())
    di[c] = di.get(c, 0) + b

keys = list(sorted(di.keys(), reverse=True))
ichi = 0
for i in range(N):
    try:
        if keys[ichi] > As[i]:
            As[i] = keys[ichi]
            di[keys[ichi]] -= 1
        else:
            break
        if di[keys[ichi]] == 0:
            ichi += 1
    except:
        pass
print(sum(As))
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    s.append(''.join(sorted(input())))
s.sort()
ans = 0
for i in range(N):
    for j in range(i+1, N):
        if s[i] == s[j]:
            ans += 1
        elif s[i] < s[j]:
            break
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
s = []
for i in range(N):
    s_i = ''.join(sorted(input()))
    s.append(s_i)

s.sort()
ans = 0
for i in range(N):
    ans += bisect.bisect_right(s, s[i])-i-1
    # for j in range(i+1, N):
    #     if s[i] == s[j]:
    #         ans += 1
    #     elif s[i] < s[j]:
    #         break
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    n, k = map(int, input().split())
    d = 60
    to = [[0]*(n) for _ in range(d)]
    to[0] = list(map(lambda x: int(x) - 1, input().split()))
    for i in range(d-1):
        for j in range(n):
            to[i+1][j] = to[i][to[i][j]]
    
    v = 0
    for i in range(d, -1 , -1):
        l = pow(2, i)
        if l <= k:
            v = to[i][v]
            k -= l
    print(v+1)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(lambda x: int(x)-1, input().split()))
    now = 0
    dict_ = {}
    stack = []
    for i in range(N):
        if now not in dict_:
            dict_[now] = A[now]
            stack.append(now)
            now = A[now]
        else:
            idx = stack.index(now)
            mod = i - idx
            break
    idx = idx + (K-idx) % mod
    idx = min(K, idx)
    print(stack[idx]+1)


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

import sys
input = sys.stdin.readline
N , W = map(int , input().split())
weight = []
value = []
for _ in range(N):
    w , v = map(int , input().split())
    weight.append(w)
    value.append(v)

def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]
    def solve(i,w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1,w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1,w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    solve(0,W)
    #print(dp)
    return max(dp[0])

if __name__ == "__main__":
    print(knapsack())

### FIXED CODE ###

import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i,:]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))
### BUGGY CODE ###

import sys 
MOD = 10 ** 9 + 7
INF = 10**5
from collections import deque

def main():
    n = int(input())
    dist = []
    edge = []
    ans = 0
    for i in range(n):
        a = list(map(int,input().split()))
        dist.append(a)
        for j in range(n):
            if i < j:
                edge.append((a[j],i,j))
                ans += a[j]
    
    for k in range(n - 1):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] ,dist[i][k] + dist[k][j])
    
    edge.sort(reverse = True,key = lambda x:x[0])
    for c,a,b in edge:
        if dist[a][b] < c:
            ans = -1
            break
        for i in range(n):
            if i != a and i != b:
                if c == dist[a][i] + dist[i][b]:
                    ans -= c
                    break
    print(ans)   

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys 
MOD = 10 ** 9 + 7
INF = 10**5
from collections import deque

def main():
    n = int(input())
    dist = []
    edge = []
    ans = 0
    for i in range(n):
        a = list(map(int,input().split()))
        dist.append(a)
        for j in range(n):
            if i < j:
                edge.append((a[j],i,j))
                ans += a[j]
    
    for k in range(n - 1):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] ,dist[i][k] + dist[k][j])
    
    edge.sort(reverse = True,key = lambda x:x[0])
    for c,a,b in edge:
        if dist[a][b] < c:
            ans = -1
            break
        for i in range(n):
            if i != a and i != b:
                if c == dist[a][i] + dist[i][b]:
                    ans -= c
                    break
    print(ans)   

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

n = int(input())

input_patterns = []

patterns = {}

a_max = ord('z')
a_min = ord('a')


def init_key():
    ini_key = []
    for i in range(26):
        ini_key.append(0)
    return ini_key

for i in range(n):
    val = input()
    input_patterns.append(val)

#input_patterns = ['acornistnt', 'peanutbomb', 'constraint']
count = 0
for inp in input_patterns:
    key = init_key()
    for j in range(len(inp)):
        # make [0, 0, 1, 0, 2, 3, ...]
        #       a  b  c  d  e  f  
        for k in range(26):
            if inp[j] == chr(ord('a') + k):
                key[k] = key[k] + 1

    skey = ''
    for k in range(26):
        skey = skey + str(key[k])

    if skey in patterns:
        patterns[skey] = patterns[skey] + 1
    else:
        patterns[skey] = 1

    if patterns[skey] > 1:
        count = count + patterns[skey] - 1

        
result = 0

#for skey in patterns:
#    if patterns[skey] > 1:
#        for i in range(1, int(patterns[skey])):
#            result = result + i

print('{}'.format(count))


### FIXED CODE ###

n = int(input())

input_patterns = []

patterns = {}

def init_key():
    ini_key = []
    for i in range(26):
        ini_key.append(0)
    return ini_key

for i in range(n):
    val = input()
    input_patterns.append(val)

count = 0
for inp in input_patterns:
    key = sorted(inp)
    skey = ''

    for k in range(len(key)):
        skey = skey + key[k]

    if skey in patterns:
        patterns[skey] = patterns[skey] + 1
    else:
        patterns[skey] = 1

    if patterns[skey] > 1:
        count = count + patterns[skey] - 1
    
print('{}'.format(count))
### BUGGY CODE ###

from collections import Counter
import numpy as np

n, m = map(int, input().split())

tar = [1] * (1 + 10 ** 5)
tar = np.array(tar)

for i in range(m):
    l, r = map(int, input().split())
    tar[:l-1] = 0
    tar[r:] = 0

#tar = tar.tolist()
# print(tar[0:5])
count = Counter(tar)
ans = count[1]
print(ans)


### FIXED CODE ###

from collections import Counter
import numpy as np

n, m = map(int, input().split())
data = [0] * m

for i in range(m):
    data[i] = list(map(int, input().split()))


data = np.array(data)
ll = data[:, 0]
rr = data[:, 1]

ans = np.min(rr) - max(ll) + 1
ans = max(0, ans)
print(ans)

'''
n, m = map(int, input().split())
tar = [0] * (1 + 10 ** 5)
tar = np.array(tar)

for i in range(m):
    l, r = map(int, input().split())
    tar[l:r + 1] += 1
    #print(tar[:10])

#tar = tar.tolist()
# print(tar[0:5])
count = Counter(tar)
ans = count[m]
print(ans)
#-----------------------------
n, m = map(int, input().split())

ll, rr = map(int, input().split())
for i in range(m - 1):
    l, r = map(int, input().split())

    #lについて
    if (l <= ll):
      pass
    elif (ll < l )

ans = max(ll - rr, 0)
print(ans)

'''
### BUGGY CODE ###

import collections

n = int(input())
s = str(input())

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

s = s.replace("R", "0").replace("G", "1").replace("B", "2")

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

count = 0
for i in range(n):
  for j in range(i+1, n):
    if 2*j - i <= n-1:
      a = int(s[i])
      b = int(s[j])
      c = int(s[2*j-i])
      if noteq(a, b, c):
        count += 1
    
ans = s_r * s_g * s_b - count
print(ans)

### FIXED CODE ###

import collections

n = int(input())
s = str(input())

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

ans = s_r * s_g * s_b

for i in range(n):
  for d in range(n):
    j = i + d
    k = j + d
    if k >= n:
      break;
    else:
      a = s[i]
      b = s[j]
      c = s[k]
      if noteq(a, b, c):
        ans -= 1
    
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (-x[0], x[1]))

dp = [[0 for x in range(m)] for y in range(n)]

for i in range(n):
    a, b = xys[i]
    # print(i, a, b)
    if i == 0:
        for j in range(0, m - a + 1):
            dp[i][j] = b
    else:
        dp[i][0] = max(dp[i - 1][0], b)
        for j in range(1, m - a + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + b)
    # print(dp[i])

# print(dp)
print(max(max(x) for x in dp))


### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (x[0], -x[1]))

ans = 0

j = 0
h = []
for i in range(1, m + 1):
    while j < len(xys) and xys[j][0] <= i:
        heappush(h, -xys[j][1])
        j += 1
    if h:
        x = -heappop(h)
        # print("Pick", x)
        ans += x

print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))

l.sort()

cnt = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i] + l[j] > l[k] and l[i] + l[k] > l[j]:
                cnt += 1

print(cnt)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))

l.sort()
# print(l)

cnt = 0

for i in range(n):
    for j in range(i+1, n-1):
        t = l[i] + l[j]
        idx = bisect.bisect_left(l, t)
        cnt += idx - (j + 1)
print(cnt)
### BUGGY CODE ###

s = input()
ls = [char for char in s]
while True:
    if ls[0] != 'A':
        ls.pop(0)
    else:
        break
while True:
    if ls[-1] != 'Z':
        ls.pop(-1)
    else:
        break

print(len(ls))


### FIXED CODE ###

s = input()

for i in range(len(s)):
    if s[i] == 'A':
        a_index = i
        break

for j in range(-1, -(len(s)-a_index), -1):
    if s[j] == 'Z':
        z_index = j
        break

length = (len(s) + z_index) - a_index + 1
print(length)
### BUGGY CODE ###

import itertools

N = int(input())
S = input()

R = [i for i, x in enumerate(S) if x == "R"]
G = [i for i, x in enumerate(S) if x == "G"]
B = [i for i, x in enumerate(S) if x == "B"]

RGB = list(itertools.product(R,G, B))

result = 0
for item in RGB:
    s_item = sorted(item)
    if s_item[2] - s_item[1] != s_item[1] - s_item[0]:
        result += 1

print(result)

### FIXED CODE ###

import itertools

N = int(input())
S = input()

r_cnt = S.count("R")
g_cnt  = S.count("G")
b_cnt = S.count("B")

ans = r_cnt * g_cnt * b_cnt

for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k >= N:
            break
        if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
            ans -= 1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(1, Q+1):
    query = input()
    if len(query) == 1:
        S = S[::-1]
    else:
        n, F, C = query.split()
        if F == '1':
            s_list = [C, S]
        else:
            s_list = [S, C]
        S = ''.join(s_list)
print(S)

### FIXED CODE ###

from collections import deque
S = list(input())
Q = int(input())

d = deque()
d.extend(S)
cnt = 0
for i in range(1, Q+1):
    query = input()
    if len(query) == 1:
        cnt += 1
    else:
        n, F, C = query.split()
        if cnt % 2 == 0:  # 反転cntが偶数,F=1で末尾
            if F == '1':
                d.appendleft(C)
            else:
                d.append(C)
        else:  # 反転cntが偶数,F=1で先頭
            if F == '1':
                d.append(C)
            else:
                d.appendleft(C)

if cnt % 2 == 1:  # cnt奇数の場合、反転
    d.reverse()
else:
    pass

l = list(d)
S = ''.join(l)
print(S)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = input()
    if q[0] == '1':
        S = ''.join(list(reversed(S)))
    else:
        T, F, C = q.split()
        S = C + S if F == '1' else S + C
print(S)

### FIXED CODE ###

S = list(input())
Q = int(input())
f = list()
b = list()
r = False
for i in range(Q):
    q = input()
    if q[0] == '1':
        r = not r
    else:
        T, F, C = q.split()
        if (F == '1') ^ r:
            f.append(C)
        else:
            b.append(C)
if r:
    S = list(reversed(S + b)) + f
else:
    S = list(reversed(f)) + S + b

print(''.join(S))
### BUGGY CODE ###

import copy

N,M = map(int,input().split())
pref = [[] for i in range(N)]
id = [[]] * M

for i in range(M):
  p,y = map(int,input().split())
  id[i] = [p,y]
  pref[p - 1].append(y)
  #pref[p - 1] = sorted(pref[p - 1])

for i in range(N):
  pref[i] = sorted(pref[i])

for i in range(M):
  p = id[i][0]
  y = id[i][1]
  order = str(pref[p -  1].index(y) + 1)
  city = str(p)
  ID = ""
  ID += "0" * (6 - len(city)) + city + "0" * (6 - len(order)) + order
  print(ID)


### FIXED CODE ###

N,M = map(int,input().split())

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

for i in range(M):
  L[i].append(i + 1)

sortL = sorted(L)

ID = ""

order = 0

for i in range(0,len(L)):
  if sortL[i][0] > sortL[i-1][0]:
    order = 0
  order += 1
  pref = str(sortL[i][0])
  ID = "0" *  (6 - len(pref))
  ID += pref
  ID += "0" * (6 - len(str(order)))
  ID += str(order)
  sortL[i].append(ID)

sortL.sort(key=lambda x: x[2])

for i in range(0,len(L)):
  print(sortL[i][-1])
### BUGGY CODE ###

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i:i+k][0] - h[i:i+k][k-1]
    if seed > high:
        seed = high

print(seed)

### FIXED CODE ###

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i] - h[i+k-1]
    seed = min(high,seed)

print(seed)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())

for k in range(1,n+1):
    s = k*(k+1)//2
    if s==n:
        res = set(range(1,k+1))
        break
    if s>=n and (s-n)<=k:
        res = set(range(1,k+1))
        res.remove(s-n)

for r in res:
    print(r)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())

for k in range(1,n+1):
    s = k*(k+1)//2
    if s==n:
        res = set(range(1,k+1))
        break
    if s>=n and (s-n)<=k:
        res = set(range(1,k+1))
        res.remove(s-n)
        break

for r in res:
    print(r)
### BUGGY CODE ###

import sys
p = [r for r in sys.stdin.read().split('\n') if r != '']
n = int(p[0])
s = p[1:]
for i, r in enumerate(s):
    s[i] = ''.join(sorted((c for c in r)))
total = 0
while len(s):
    a = s.pop(-1)
    count = 0
    for i in reversed(range(0, len(s))):
        if s[i] == a:
            count += 1
            s.pop(i)
    total += int((count + 1) * count / 2)
print(total)

### FIXED CODE ###

import sys
p = [r for r in sys.stdin.read().split('\n') if r != '']
n = int(p[0])
s = p[1:]
for i, r in enumerate(s):
    t = list(r)
    t.sort()
    s[i] = ''.join(t)
d = {}
for i in s:
    if i in d:
        d[i] += 1
    else:
        d[i] = 0
count = 0
for k, v in d.items():
    count += int((v + 1) * v / 2)
print(count)
### BUGGY CODE ###

import numpy as np

n = int(input())

i = np.array([i+1 for i in range(n)])

ps = [i+1 for i in range(1, n)] + [1]

ps = np.array(ps)

ms = i % ps

print(np.sum(ms))


### FIXED CODE ###

n = int(input())

if n == 1:
    print(0)
else:
    ans = n *(n-1) // 2
    print(ans)
### BUGGY CODE ###

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = [[0 for _ in range(x+1)] for _ in range(n+1)]
dp[0][x] = 1
for i in range(n):
	for j in range(x+1):
		dp[i+1][j] += (n-1-i) * dp[i][j]
		dp[i+1][j%s[i]] += dp[i][j]
	for j in range(x+1):
		dp[i+1][j] %= MOD
#print(dp)
ans = 0
for j in range(x+1):
	ans += dp[n][j] * j
	ans %= MOD
print(int(ans))

### FIXED CODE ###

import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]

MOD = 1e9+7
n, x = map(int, input().split())
s = list(map(int, input().split()))
s.sort(reverse=True)
dp = defaultdict(int)
dp[x] = 1
for i in range(n):
	ss = s[i]
	dpp = defaultdict(int)
	for key, value in dp.items():
		dpp[key] += (n-1-i) * value
		dpp[key%ss] += value
	for key in dpp.keys():
		dpp[key] %= MOD
	dp = dpp
ans = 0
for key, value in dp.items():
	ans += value * key
	ans %= MOD
print(int(ans))
### BUGGY CODE ###

mod = 10 ** 6 + 3

#TLE
def solve():
    x, d, n = map(int, input().split())
    ans = 1
    for i in range(n):
        ans *= (x+i*d)
        ans %= mod
    print(ans)
    return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()

### FIXED CODE ###

mod = 10 ** 6 + 3


class Combi():
    def __init__(self, N, mod):
        self.power = [1 for _ in range(N+1)]
        self.rev = [1 for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.power[i] = (self.power[i-1]*i) % self.mod
        self.rev[N] = pow(self.power[N], self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.rev[j-1] = (self.rev[j]*j) % self.mod

    def com(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.power[K])*(self.rev[K-R])*(self.rev[R])) % self.mod

    def pom(self, K, R):
        if K < R:
            return 0
        else:
            return (self.power[K])*(self.rev[K-R]) % self.mod

    def powe(self, K):
        return self.power[K]

    def rev_powe(self, K):
        return self.rev[K]


combi = Combi(mod-1, mod)


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


def count_div(L, R, D):
    return not bool(R//D - (L-1)//D)


def solve():
    x, d, n = map(int, input().split())
    if d % (mod) == 0:
        print(pow(x,n,mod))
        return
    elif d % (mod) != 0:
        y = rev(d)*x
        if count_div(y, y+n-1, mod):
            y = y % mod
            ans = pow(d, n, mod)*combi.powe(y+n-1) * combi.rev_powe(y)*y
            print(ans % mod)
            return
        else:
            ans = 0
            print(ans % mod)
            return


def main():
    Q = int(input())
    for i in range(Q):
        solve()


if __name__ == "__main__":
    main()
### BUGGY CODE ###

k = int(input())
def gcd(a, b):
    while b > 0:
        r = a%b
        a = b
        b = r
    return a
s = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for z in range(1,k+1):
            s+=gcd(gcd(i,j),z)
print(s)

### FIXED CODE ###

from math import gcd
k = int(input())
s = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        a = gcd(i,j)
        for z in range(1,k+1):
            s+=gcd(a,z)
print(s)