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

import sys
read = sys.stdin.buffer.read
 
mod = 998244353 
U, S, *A = map(int, read().split())

dp = [[[0]*3 for i in range(3001)] for i in range(3001)]

dp[0][0][0] = 1;
for i in range(U):
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]%mod
        dp[i+1][j][1] += dp[i+1][j][0] + dp[i][j][1]%mod
        dp[i+1][j][2] += dp[i+1][j][1] + dp[i][j][2]%mod
        if j - A[i] >= 0:
            dp[i+1][j][1] += dp[i][j-A[i]][0]%mod + dp[i][j-A[i]][1]%mod
            dp[i+1][j][2] += dp[i][j-A[i]][0]%mod + dp[i][j-A[i]][1]%mod
    
    
print(dp[U][S][2])

### FIXED CODE ###

def main():
  import sys
  read = sys.stdin.buffer.read
  r = 998244353
  U, S, *A = map(int, read().split())
  import copy
  ans = 0
  f = [0]*3010
  for a in A:
      c = copy.copy(f)
      f = [0]*a+c[:-a]
      f = [x+y for x,y in zip(f,c)]
      f[0] += 1
      f[a] += 1
      ans += f[S]
  ans %= r
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

x,y = 0,0
#a_L = list(sorted(a_L))
ans = float("inf")
g = sum(a_L)
for i in range(1,len(a_L)):
    x = sum(a_L[0:i])
    g = sum(a_L[i:])
    ans = min(abs(x-g),ans)

print(ans)

### FIXED CODE ###

import itertools
n = int(input())
a_L = list(map(int,input().split()))

def get_ruisekiwa(a_L):
    # 累積和
    return [0] + list(itertools.accumulate(a_L))

ans = float("inf")
r = get_ruisekiwa(a_L)

#print(r)
for i in range(1,len(a_L)):
    x = r[i]
    g = r[-1] - r[i]
    ans = min(abs(x-g),ans)

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

N = int(input())
X = list(map(int,input().split()))
S = []
dp = [1]
mod = 10**9+7
for i in range(N):
    t = i+1
    dp.append(dp[i]*t)
ans = 0
for i in range(N-1):
    x = X[i]
    S.append(X[N-1]-x)
ans = 0
for i in range(N-1):
    x = S[i]
    t = i + 1
    ans += dp[N-1]//t*x%mod
print(ans%mod)

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
S = []
dp = [1]
mod = 10**9+7
for i in range(N):
    t = i+1
    dp.append(dp[i]*t%mod)
def power(a,b):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power(a,b//2)
        return d*d%mod
    elif b % 2 == 1:
        return a*power(a,b-1)%mod
W = []
for i in range(1,N):
    y = dp[N-1]*power(i,mod-2)%mod
    W.append(y)
ans = 0
for i in range(N-1):
    x = X[i]
    S.append(X[N-1]-x)
ans = 0
for i in range(N-1):
    x = S[i]
    t = i + 1
    ans += W[i]*x%mod
print(ans%mod)
### BUGGY CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=np.uint32)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
matmul = np.zeros((n, n), dtype=np.uint32)
matmul[n-1] = mat[n-1]
for i in range(n-2, -1, -1):
    matmul[i] = matmul[i+1] + mat[i]

matmul = matmul.T
matmul2 = np.zeros((n, n), dtype=np.uint32)
matmul2[0] = matmul[0]
for i in range(n-1):
    matmul2[i+1] = matmul2[i] + matmul[i+1]

matmul2 = matmul2.T

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)

### FIXED CODE ###

import numpy as np

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

mat = np.zeros((n, n), dtype=int)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipud(matmul)
matmul2 = np.cumsum(matmul, axis=1)

for i in range(q):
    p, q = map(int, input().split())
    ans = matmul2[p-1, q-1]
    print(ans)
### BUGGY CODE ###

from itertools import product
N,M = map(int,input().split())
G = {i:[] for i in range(M)}
for i in range(M):
    a,b = map(int,input().split())
    G[i] = [a,list(map(int,input().split()))]
A = {S:{tuple(G[j][1]):[0] for j in range(M)} for S in product((0,1),repeat=N) }
for S in product((0,1),repeat=N):
    for j in range(M):
        B = [0 for _ in range(N)]
        for x in G[j][1]:
            B[x-1] = 1
        C = list(S[:])
        for i in range(N):
            if C[i]==1 and B[i]==1:
                C[i] = 0
        A[S][tuple(G[j][1])] = tuple(C)
INFTY = 10**11
dp = {j:{S:INFTY for S in product((0,1),repeat=N)} for j in range(M+1)}
for j in range(M+1):
    dp[j][tuple([0 for _ in range(N)])] = 0
for j in range(M):
    for S in product((0,1),repeat=N):
        dp[j+1][S] = min(dp[j][S],dp[j][A[S][tuple(G[j][1])]]+G[j][0])
s = tuple([1 for _ in range(N)])
a =dp[M][s]
if a>=INFTY:
    print(-1)
else:
    print(a)

### FIXED CODE ###

from itertools import product
N,M = map(int,input().split())
G = {i:[] for i in range(M)}
for i in range(M):
    a,b = map(int,input().split())
    G[i] = [a,list(map(int,input().split()))]
INFTY = 10**11
dp = [[INFTY for S in range(2**N)] for _ in range(M+1)]
for j in range(M+1):
    dp[j][0] = 0
for j in range(M):
    for S in range(2**N):
        y = 0
        for x in G[j][1]:
            y += 2**(x-1)
        dp[j+1][S] = min(dp[j][S],dp[j][S&(~y)]+G[j][0])
a =dp[M][2**N-1]
if a>=INFTY:
    print(-1)
else:
    print(a)
### BUGGY CODE ###

from collections import Counter

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	n=int(inputs[0][0])
	aa=getIntList(inputs[1])
	
	count=Counter(aa)
	
# 	print(n)
# 	print(aa)
# 	print(count0)
	
	ans={}
	pat={}
	for k in range(n):
		targetA=aa[k]
		if targetA in ans:
			print(ans[targetA])
			continue
		
		count[targetA]-=1
		n=0
		for ai,c in count.items():
			if c in pat:
				ni=pat[c]
			else:
				ni=c*(c-1)//2
				pat[c]=ni
			n+=ni
		ans[targetA]=n
		print(n)
		count[targetA]+=1
		
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)



### FIXED CODE ###



#####

import numpy as np
# from numpy import int64, int8
from collections import Counter

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
# import sys
# sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def unique(x):
	count=Counter()
	for xi in x:
		count[xi]+=1
	u,c=zip(*count.items())
	return u,c



def main(inputs):
	n=int(inputs[0][0])
	aa=getIntList(inputs[1])

# 	n=200000
# 	aa=np.random.randint(1,n+1,n)
	
# 	print("start")
# 	aa=np.array(aa)
# 	aUnique, count=np.unique(aa, return_counts=True)

	aUnique, count=unique(aa)
	aUnique=np.array(aUnique, np.int64)
	count=np.array(count, np.int64)
	
# 	print(n)
# 	print("aa",aa)
# 	print("aUnique",aUnique)
# 	print("count  ",count)
	
# 	countUnique,countCount=np.unique(count, return_counts=True)
	countUnique,countCount=unique(count)
	countCount=np.array(countCount, np.int64)
	
	pat={}
	countAns=np.empty(len(countUnique), np.int64)
	countAns1=np.empty(len(countUnique), np.int64)
	for ci,c in enumerate(countUnique):
		if c not in pat:
			ni=c*(c-1)//2
			pat[c]=ni
		countAns[ci]=pat[c]
		
		c-=1
		if c not in pat:
			ni=c*(c-1)//2
			pat[c]=ni
		countAns1[ci]=pat[c]
	
# 	print("countUnique",countUnique)
# 	print("countCount ",countCount)
# 	print("countAns ",countAns)
# 	print("countAns1",countAns1)
	
	countUniqueIndex=dict([(c,i) for i,c in enumerate(countUnique)])
# 	print("countUniqueIndex", countUniqueIndex)
	
# 	uniNums=np.empty(len(aUnique), np.int64)
	nums=np.empty(n, np.int64)
	ans={}
	for cui,cu in enumerate(countUnique):
		countCount[cui]-=1
		num0=(countAns*countCount).sum()
		countCount[cui]+=1
		num1=countAns1[cui]
		num=num0+num1
# 		print(cu,num)
		countMask=count==cu
# 		uniNums[countMask]=num
		targetA=aUnique[countMask]
# 		print(targetA)
		for a in targetA:
			ans[a]=num
# 		print(targetA[None,:])
# 		print(aa[:,None])
# 		aMask=(aa[:,None]==targetA[None,:]).any(axis=1)
# 		print(aMask)

# 		nums[aMask]=num
# 	print("\n".join(map(str,nums)))

	for a in aa:
		print(ans[a])
	

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

ss = input().split()
N = int(ss[0])
K = int(ss[1])
Q = int(ss[2])
As = []
for i in range(Q):
  As.append(int(input()))
SCORE = [K] * N
for i in range(Q):
  XX = map(lambda x: x - 1, SCORE)
  SCORE = list(XX)
  SCORE[As[i]-1] += 1
for i in range(N):
  if(SCORE[i]<1):
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

ss = input().split()
N = int(ss[0])
K = int(ss[1])
Q = int(ss[2])
As = []

SCORE = [0] * N

for i in range(Q):
  SCORE[int(input())-1] += 1
for i in range(N):
  if(SCORE[i]<= Q-K):
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

n=int(input())
hoge={}
for i in range(n):
  tmp=input()
  if(tmp in  hoge):
    hoge[tmp]+=1
  else:
    hoge[tmp]=1
keys = [k for k, v in hoge.items() if v ==max(hoge.values())]
hoge=sorted(keys)
for i in range(len(hoge)):
  print(hoge[i])


### FIXED CODE ###

n=int(input())
hoge={}
for i in range(n):
  tmp=input()
  if(tmp in  hoge):
    hoge[tmp]+=1
  else:
    hoge[tmp]=1
    
key_max=max(hoge.values())
keys = [k for k, v in hoge.items() if v ==key_max]
hoge=sorted(keys)
for i in range(len(hoge)):
  print(hoge[i])
### BUGGY CODE ###

import sys
S =input()
Q=int(input())
orders=[]
for line in sys.stdin.readlines():
    #print(line)
    orders.append(line.rstrip().split(" "))
#print(orders)
for order in orders:
    if order[0]=="1":
        #print(1)
        S=S[::-1]
    elif order[0]=="2" and order[1]=="1":
        #print(2)
        S=order[2]+S
    elif order[0]=="2" and order[1]=="2":
        #print(3)
        S=S+order[2]
print(S)

### FIXED CODE ###

import sys
S =input()
Q=int(input())
orders=[]
for line in sys.stdin.readlines():
    orders.append(line.rstrip().split(" "))
dire=1
right=""
left=""
center=""
for order in orders:
    if order[0]=="1":
        dire=dire*(-1)
        center=right
        right=left
        left=center
    elif order[0]=="2" and order[1]=="1":
        if dire==1:
            left=order[2]+left
        if dire==-1:
            left=left+order[2]
    elif order[0]=="2" and order[1]=="2":
        if dire==1:
            right=right+order[2]
        if dire==-1:
            right=order[2]+right
if dire==1:
    S=S
    right=right
    left=left
elif dire==-1:
    S=S[::-1]
    right=right[::-1]
    left=left[::-1]
print(left+S+right)
### BUGGY CODE ###

ks= list(map(int, input().split())) 
 
count = 0

from itertools import product

xs = range(0,ks[0]+1)
ys = range(0,ks[0]+1)
zs = range(0,ks[0]+1)

for x, y, z in product(xs, ys, zs):
  if x+y+z == ks[1]:
    count+=1

print(count)
  

### FIXED CODE ###

ks= list(map(int, input().split())) 
 
count = 0
 
x = 0
y = 0
z = 0
 
for targetX in range(ks[0]+1):
    
    
    if targetX <= ks[0] and ks[1]-(targetX+ks[0]+ks[0]) <= 0:
    
        for targetY in range(ks[0]+1):
            
            z = ks[1] - (targetX + targetY)
            
            if 0 <= z and z <= ks[0]:
                count += 1
                
        
        
        
 
print(count)
### BUGGY CODE ###

a,b,k=list(map(int,input().split()))
l=[]
v=[]
for i in range(a,b+1):
    l.append(i)
for i in range(k):
    if i>=len(l):
        break
    v.append(l[i])
l.reverse()
for i in range(k-1,-1,-1):
    if i>=len(l):
        continue
    v.append(l[i])
s=set(v)
l=list(s)
l.sort()
for i in l:
    print(i)

### FIXED CODE ###

A,B,K=list(map(int,input().split()))
L=[]
k=0
for i in range(A,B+1):
    L.append(i)
    k+=1
    if(k>=K):
        break

k=0
for i in range(B,A-1,-1):
    L.append(i)
    k+=1
    if(k>=K):
        break

S=set(L)
for s in sorted(list(S)):
    print(s)
### BUGGY CODE ###

N,K = map(int, input().split())
A = [list(map(int,input().split())) for i in range(N)]

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr

B=[]
for i in range(N):
    B.append(A[i][0])
    
C=bubble_sort(B)

ans = C[K-1] - C[0]
for i in range(N-K+1):
    if ans > C[i+K-1] -C[i]:
        ans = C[i+K-1] -C[i]
        
print(ans)

### FIXED CODE ###


N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

import numpy as np
N, D, A = list(map(int, input().split()))
X = np.ones(N)
H = np.ones(N)
for i in range(N):
  X[i], H[i] = list(map(int, input().split()))

H = H[X.argsort()]
X = np.sort(X)

min_n = 0

for i in range(N):
  if H[i] <= 0:
    continue
  in2Di = np.abs(X - X[i]) <= 2 * D
  ni = int(H[i]/A) if H[i] % A == 0 else int(H[i]/A) + 1
  H[in2Di] -= A * ni
  min_n += ni
  
print(min_n)

### FIXED CODE ###

from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    # 期限切れの蓄積ダメージを削除
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * D, need])

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

import sys
input = sys.stdin.readline
H,W,N = map(int,input().split())
count = []
L = 0
for i in range(N):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(max(0,a-2),min(a+1,H-2)):
        for j in range(max(0,b-2),min(b+1,W-2)):
            count.append((i,j))
            L += 1
count.sort()
ans = [0]*10
tmp = 1
for i in range(L-1):
    if count[i] == count[i+1]:
        tmp += 1
    else:
        ans[tmp] += 1
        tmp = 1
if L>=1:
  ans[tmp] += 1
ans[0] = (H-2)*(W-2)-sum(ans)
for i in range(10):
    print(ans[i])

### FIXED CODE ###

H,W,N = map(int,input().split())
count = []
L = 0
for i in range(N):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(max(0,a-2),min(a+1,H-2)):
        for j in range(max(0,b-2),min(b+1,W-2)):
            count.append((i,j))
            L += 1
count.sort()
ans = [0]*10
tmp = 1
for i in range(L-1):
    if count[i] == count[i+1]:
        tmp += 1
    else:
        ans[tmp] += 1
        tmp = 1
if L>=1:
  ans[tmp] += 1
ans[0] = (H-2)*(W-2)-sum(ans)
for i in range(10):
    print(ans[i])
### BUGGY CODE ###

S = input()
Rindex = [i for i,x in enumerate(S) if x == 'R']
Lindex = [i for i,x in enumerate(S) if x == 'L']
res = [0 for i in range(len(S))]
for i in range(len(S)):
    if S[i] == 'R':
        for l in Lindex:
            if l>i:
                a = l
                break
                
        c = a - i - 1
        if c%2 == 0:
            res[a - 1] += 1
        else:
            res[a] += 1
    else:
        for r in Rindex[::-1]:
            if r<i:
                a = r
                break
        c = i - a - 1
        if c%2 == 0:
            res[a + 1] += 1
        else:
            res[a] += 1
for i,r in enumerate(res):
    if i != len(res) -1:
        print(r, end=" ")
    else:
        print(r)

### FIXED CODE ###

S = input()
Rnum = S.split('L')
Rnum = [len(i) for i in Rnum if i != '']
Lnum = S.split('R')
Lnum = [len(i) for i in Lnum if i != '']
res = [0]*len(S)
count = 0
for i,r in enumerate(Rnum):
    l = Lnum[i]
    res[r+count-1] = int((r+1)/2) + int(l/2)
    res[r+count] = int(r/2) + int((l+1)/2)
    count += r+l
for i,r in enumerate(res):
    if i!= len(res)-1:
        print(r,end=' ')
    else:
        print(r)
### BUGGY CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
c = collections.Counter(a)

a1=len(list(set(a)))

total=0
for j in range(a1):
    x=c.most_common()[j][1]
    total+=x*(x-1)/2

for i in range(n):
    ans=total-a.count(a[i])+1
    print(int(ans))

### FIXED CODE ###

import collections 
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
c=defaultdict(int)
for s in a:
    c[s]+=1

a1=list(set(a))

total=0
for j in range(len(a1)):
    x=c[a1[j]]
    total+=x*(x-1)/2

for i in range(n):
    ans=total-c[a[i]]+1
    print(int(ans))
### BUGGY CODE ###

n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i == n):continue
            a.append(n//i)
        i += 1
    return a

ans = 0
a = divisior(n)

for x in a:
    if x == 1: continue
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

print(ans)




### FIXED CODE ###

n = int(input())

def divisior(n):
    a = []
    i = 1
    while (i*i <= n):
        if n%i == 0:
            a.append(i)
            if (i*i != n): a.append(n//i)
        i += 1
    return a

ans = 0
a = divisior(n)

for x in a[1:]:
    tmp = n
    while (tmp%x == 0): tmp = tmp//x
    if (tmp%x == 1) : ans += 1

b = divisior(n-1)

ans = ans + len(b) -1

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

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
     n,m,k = map(int,input().split())
     a = (cmb(n*m-2,k-2)%(10**9+7))*(n*m*(m*(n**2-1)+n*(m**2-1)))//6
     print(a%(10**9+7))
     return 0

if __name__=="__main__":
     main()

### FIXED CODE ###

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

mod = 10**9+7 #出力の制限
N = 10**6
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 )

n,m,k = map(int,input().split())
nm = n*m%(10**9+7)
k = k%(10**9+7)
a = (cmb(nm-2,k-2,mod)%(10**9+7))*(nm*(m*(n**2-1)+n*(m**2-1)))//6
print(a%(10**9+7))
### BUGGY CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
th = Counter(st[:n])["W"] + Counter(st[n+1:])["E"]
previous = st[0]
for i in range(1,n):
    temp = ma[::-1][0]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
    if(th-(n-i) > min(ma)):
        break
print(min(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
                    if (nx == Dh) and (ny == Dw):
                        print(res_S[Dh - 1][Dw - 1])
                        exit()
        que_warp.pop(0)

print (res_S[Dh-1][Dw-1])

### FIXED CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    l = len(que)
    while (que):
        if l > 0:
            que_warp.append(que[0])
            l -= 1
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])
### BUGGY CODE ###

from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

Max = mod-1
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod
def pow_mod(x,n):
    if n==0: return 1
    if n%2:return x*pow_mod(x,n-1)%mod
    a = pow_mod(x,n//2)
    return a*a%mod

Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow_mod(x,n)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))

### FIXED CODE ###

from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


Max = mod
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod


Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow(x,n,mod)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n,mod)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))