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

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0

for i in range(1, n):
    tmp = float("inf")
    hi = h[i]
    for j in range(max(i - k, 0), i):
        res = dp[j] + abs(hi - h[j])
        if tmp > res:
            tmp = res
    dp[i] = tmp

print(dp[n - 1])

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    B()
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    ans = -1
    for n in range(M)[N:]:
        for i in range(M + 1)[n + 1:]:
            mod = n * i % 2019
            if ans < 0 or mod < ans:
                ans = mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    ans = -1
    for n in range(M)[N:]:
        for i in range(M + 1)[n + 1:]:
            mod = n * i % 2019
            if ans < 0 or mod < ans:
                ans = mod
                if ans == 0:
                    break
        if ans == 0:
            break
    print(ans)


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

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

for i in range(U+1,0,-1):
    if(M%i==0):
        if((M//i)>=N):
            print(i)
            exit()


### FIXED CODE ###

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

for i in range(M//N +1,0,-1):
    if(M%i==0):
        if((M//i)>=N):
            print(i)
            exit()
### BUGGY CODE ###

def muridesu():
    N,K=[int(_) for _ in input().split()]
    aA=[int(_) for _ in input().split()]
    dsA = set(aA)
    def f(i,aA):
        return sum(i^a for a in aA)
    print(max(f(k,aA) for k in (set(range(1,K+1)) - dsA  | {0})))
muridesu()


### FIXED CODE ###

#場合分けがつらい
def 解():
    N,K=[int(_) for _ in input().split()]
    aD =[0]*40
    aA=[int(_) for _ in input().split()]
    iL = 0
    for i in range(40):
        m = 2**i
        aD[i]=sum((_ & m) for _ in aA)
        if aD[i]:
            iL = i
    iLK = len(bin(K))-3
    iML = max(iL,iLK)
    dp = [[0]*2 for _ in range(2)]
    #[x][0] Kに沿う
    #[x][0] Kに沿わない最大
    for i in range(iML,-1,-1):
        ib = i%2 #桁%2 dp
        inb = 0 if ib else 1 #次のdp
        i0 = aD[i] #反転しない
        i1 = (2**i)*N-i0 #反転する
        iM = max(i0,i1) #選べるとき
        bL = i < iLK #Kより長い
        if (K>>i)&1:
            dp[inb][1] = dp[ib][1] + i1
            dp[inb][0] = max(dp[ib][1] + i0 ,dp[ib][0]+(iM if bL else i0))
        else:
            dp[inb][1] = dp[ib][1] + i0
            dp[inb][0] = dp[ib][0] + (iM if bL else i0)
    print(max(dp[inb]))
解()
### BUGGY CODE ###

import numpy as np

n = int(input())

a = np.array([int(input()) for _ in range(n)])
[print(np.amax(np.hstack((a[:i], a[i+1:])))) for i in range(n)]

### FIXED CODE ###

import heapq

n = int(input())
a = [int(input()) for _ in range(n)]
a1, a2 = heapq.nlargest(2, a)
[print(a1) if _ != a1 else print(a2) for _ in a]
### BUGGY CODE ###

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

ans = 1
INF = 1000000000000000000

for a in A:
    ans *= a

if ans > INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1
INF = 1000000000000000000

if 0 in A:
    print(0)
    exit()

for a in A:
    ans *= a
    if ans > INF:
        print(-1)
        exit()

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

import math

N ,M, K = map(int,input().split())
MOD = 998244353
SUM = 0

fact = [1]
fact_inv = [1]
for i in range(1,N+1):
    fact.append(fact[-1] * i)
    fact_inv.append(pow(fact[-1],MOD-2,MOD))

def combinations_count(n, r):
    return (((fact[n] * fact_inv[n-r])%MOD) * fact_inv[r])%MOD

POW = [1]

for i in range(1,N):
    a = (POW[-1] * (M-1))%MOD
    POW.append(a)

# print(POW)
# print(POW[-1])
# print(pow(M-1,N-1,MOD))
# fact = 1#fact_(N-1)
# for i in range(N):
#     fact *= i
#     fact %= MOD




for i in range(K+1):
    if N -1 - i >= 0:
        SUM += M * POW[N-1-i] * combinations_count(N-1,i)
        SUM %= MOD

print(SUM)

### FIXED CODE ###

import math

N ,M, K = map(int,input().split())
MOD = 998244353

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs
invs = getInvs(N+3, MOD)

num = M
nums = []
for i in reversed(range(1,N)):
    nums.append(num)
    num *= i*(M-1)
    num *= invs[N-i]
    num %= MOD
nums.append(num)
nums.reverse()

ans = sum(nums[:K+1])
ans %= MOD
print(ans)
### BUGGY CODE ###

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

def ok(x):
    res = 0
    for i in range(N):
        if A[i]<0:
            left, right = -1, N
            while left + 1 < right:
                c = (left + right) // 2
                if A[c]*A[i] < x: right = c
                else:             left  = c
            res += N - right
        else:
            left, right = -1, N
            while left + 1 < right:
                c = (left + right) // 2
                if A[c]*A[i] < x: left  = c
                else:             right = c
            res += right
        if A[i]*A[i] < x:
            res -= 1
    res //= 2
    return res < K

INF = 10**18+1
l, r = -INF, INF
while l+1<r:
    x = (l+r)//2
    if ok(x):
        l = x
    else:
        r = x
print(l)


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)

A = np.sort(A)
zero = A[A == 0]
pos = A[A > 0]
neg = A[A < 0]


def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # zero and ...
    if x >= 0:
        cnt_tpl += len(zero) * N
    # positive and ...
    cnt_tpl += np.searchsorted(A, x // pos, side='right').sum()
    # negative and ...
    cnt_tpl += (N - np.searchsorted(A, (-x - 1) // (-neg), side='right')).sum()
    # a^2
    cnt_tpl -= np.count_nonzero(A * A <= x)
    assert cnt_tpl % 2 == 0
    return cnt_tpl // 2


left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= K:
        right = x
    else:
        left = x


print(right)
### BUGGY CODE ###

import itertools
#(縦, 横)
#bfs 徒歩→ワープ→徒歩→ワープ→…

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

chizu = [input() for _ in range(h)]
kabeset = set()

for i in range(h):
	for j in range(w):
		if chizu[i][j] == "#":
			kabeset.add((i, j))

settansaku = set()
stock = set()
setmada = {start}
kouho = 1
mode = 1
cost = 0

while kouho > 0:
	while kouho > 0:
		for i, j in list(setmada):
			settansaku.add((i, j))
			stock.add((i, j))
			setmada.remove((i, j))
			kouho -= 1
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if not k in kabeset:
					if 0 <= k[0]:
						if 0 <= k[1]:
							if k[0] < h:
								if k[1] < w:
									if not k in setmada:
										if not k in settansaku:
											setmada.add(k)
											kouho += 1
											if k == goal:
												mode = 0
								
	if mode == 0:
		break
	
	cost += 1
	for i, j in list(stock):
		stock.remove((i, j))
		for k in itertools.product(range(i-2, i+3), range(j-2, j+3)):
			if not k in settansaku:
				if 0 <= k[0]:
					if 0 <= k[1]:
						if k[0] < h:
							if k[1] < w:
								if not k in kabeset:
									setmada.add(k)
									kouho += 1
									if k == goal:
										mode = 0
							
	if mode == 0:
		break
	
	kouho = len(setmada)

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

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

z = []
for i in range(len(a3)):
     z.append(a.count(a3[i]))

q = 1
for i in z:
    q += i*(i-1)/2

for j in range(n):
    count = q
    count -= z[a3.index(a[j])]
    print(int(count))

### FIXED CODE ###

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

u = collections.Counter(a)

sume = 0
for i in u.values():
    sume += int(i*(i-1)/2)

for k in range(n):
    s = u[a[k]]
    print(sume-s+1)
### BUGGY CODE ###

n=int(input())
s=[0]*n
count=0
for i in range(0,n):
  temp=str(input())
  temp=sorted(list(temp))
  temp="".join(temp)
  s[i]=temp
  for j in range(0,i):
    if s[i]==s[j]:
      count=count+1
print(count)

### FIXED CODE ###

n=int(input())
dict={}
count=0
for i in range(0,n):
  temp=str(input())
  temp=sorted(list(temp))
  temp="".join(temp)
  if temp in dict:
    dict[temp]=dict[temp]+1
    count=count+dict[temp]
  else:
    dict[temp]=0
print(count)
### BUGGY CODE ###

count = 0

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

for i in range(n):
    if p[i] == min(p[:i+1]):
        count += 1

print(count)

### FIXED CODE ###

count = 0

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

min = 10**7
for i in range(n):
    if p[i] < min:
        count += 1
        min = p[i]

print(count)
### BUGGY CODE ###

from collections import Counter

n = int(input())
lst = [input() for _ in range(n)]

counter_lst = []
counter_num = []
res = 0
for i in range(n):
    a = Counter(lst[i])
    if a in counter_lst:
        m = counter_lst.index(a)
        counter_num[m] += 1
        res += counter_num[m]
    else:
        counter_lst.append(a)
        counter_num.append(0)
    
print(res)

### FIXED CODE ###

n = int(input())
lst = [input() for _ in range(n)]

dic = dict()
res = 0
for i in range(n):
    sorted_string = "".join(sorted(lst[i]))
    if sorted_string in dic:
        dic[sorted_string] += 1
        res += dic[sorted_string]
    else:
        dic[sorted_string] = 0
    
print(res)
### BUGGY CODE ###

N=int(input())
p=0
t=list(map(int,input().split()))
for i in range(N):
    k=1
    while k+i<N and t[i]&t[i+k]==0:
        t[i]+=t[i+k]
        k+=1
    p+=k
print(p)        



### FIXED CODE ###

N=int(input())
t=list(map(int,input().split()))
l=1
k=t[0]
a=0
for i in range(N):
    while l<N and k&t[l]==0:
        k+=t[l]
        l+=1
    a+=l-i
    k-=t[i]
print(a)
### BUGGY CODE ###

N=int(input())
S=input()
max=0
A = [0] *len(S)
for f in range(len(S)-1):
    i = f+1

    A[0]=len(S)
    while(i<len(S)):
        j=0
        while(i+j<len(S) and S[f+j]==S[i+j] and j<i):
            j+=1
        A[i]=j
        if(j==0):
            i+=1
            continue
        if (j > max):
            max = j
        k=1
        while(k+i<len(S) and k+A[k+j]<j):
            A[i+k]=A[f+k]
            k+=1
        i+=k
print(max)

### FIXED CODE ###

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

max = 0
index = 0
for i in range(1,len(S)-1):
    s1=S[index:i]
    s2=S[i:]
    if s1 in s2:
        max=len(s1)
    else:
        index+=1
        
print(max)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
acc[0] = 0
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        set_ans.add(acc[j+1] - acc[i])
        s = acc[j+1] - acc[i]
        index = 41
        while s:
            if s & 1:
                stand_bit[index].add(acc[j+1] - acc[i])
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
stand_bit = [set() for i in range(42)]
acc = [0 for i in range(n+1)]
for i in range(1, n+1):
    acc[i] += a[i-1] + acc[i-1]
set_ans = set()
for i in range(n):
    for j in range(i, n):
        tmp = acc[j+1] - acc[i]
        set_ans.add(tmp)
        s = tmp
        index = 41
        while s:
            if s & 1:
                stand_bit[index].add(tmp)
            s = s >> 1
            index -= 1
for i in range(42):
    if len(set_ans & stand_bit[i]) >= k:
        set_ans &= stand_bit[i]
ans_list = list(set_ans)
ans = ans_list[0]
for i in ans_list:
    ans &= i
print(ans)
### BUGGY CODE ###

from math import gcd

def gcd3(x, y, z):
    return gcd(gcd(x, y), z)

K = int(input())

if __name__ == "__main__":
    ans = 0
    for a in range(1, K+1):
        for b in range(1, K+1):
            for c in range(1, K+1):
                ans += gcd3(a, b, c)
    print(ans)

### FIXED CODE ###

k = int(input())
ans = {1: 1, 2: 9, 3: 30, 4: 76, 5: 141, 6: 267, 7: 400, 8: 624, 9: 885, 10: 1249, 11: 1590, 12: 2208, 13: 2689, 14: 3411, 15: 4248, 16: 5248, 17: 6081, 18: 7485, 19: 8530, 20: 10248, 21: 11889, 22: 13687, 23: 15228, 24: 17988, 25: 20053, 26: 22569, 27: 25242, 28: 28588, 29: 31053, 30: 35463, 31: 38284, 32: 42540, 33: 46581, 34: 50893, 35: 55362, 36: 61824, 37: 65857, 38: 71247, 39: 76884, 40: 84388, 41: 89349, 42: 97881, 43: 103342, 44: 111528, 45: 120141, 46: 128047, 47: 134580, 48: 146316, 49: 154177, 50: 164817, 51: 174438, 52: 185836, 53: 194157, 54: 207927, 55: 218812, 56: 233268, 57: 245277, 58: 257857, 59: 268182, 60: 288216, 61: 299257, 62: 313635, 63: 330204, 64: 347836, 65: 362973, 66: 383709, 67: 397042, 68: 416448, 69: 434025, 70: 456967, 71: 471948, 72: 499740, 73: 515581, 74: 536073, 75: 559758, 76: 583960, 77: 604833, 78: 633651, 79: 652216, 80: 683712, 81: 709065, 82: 734233, 83: 754734, 84: 793188, 85: 818917, 86: 846603, 87: 874512, 88: 909496, 89: 933081, 90: 977145, 91: 1006126, 92: 1041504, 93: 1073385, 94: 1106467, 95: 1138536, 96: 1187112, 97: 1215145, 98: 1255101, 99: 1295142, 100: 1342852, 101: 1373253, 102: 1422195, 103: 1453816, 104: 1502376, 105: 1553361, 106: 1595437, 107: 1629570, 108: 1691292, 109: 1726717, 110: 1782111, 111: 1827492, 112: 1887772, 113: 1925853, 114: 1986837, 115: 2033674, 116: 2089776, 117: 2145333, 118: 2197483, 119: 2246640, 120: 2332104, 121: 2379085, 122: 2434833, 123: 2490534, 124: 2554600, 125: 2609625, 126: 2693919, 127: 2742052, 128: 2813988, 129: 2875245, 130: 2952085, 131: 3003306, 132: 3096024, 133: 3157249, 134: 3224511, 135: 3306240, 136: 3388576, 137: 3444609, 138: 3533637, 139: 3591322, 140: 3693924, 141: 3767085, 142: 3842623, 143: 3912324, 144: 4027884, 145: 4102093, 146: 4181949, 147: 4270422, 148: 4361548, 149: 4427853, 150: 4548003, 151: 4616104, 152: 4718640, 153: 4812789, 154: 4918561, 155: 5003286, 156: 5131848, 157: 5205481, 158: 5299011, 159: 5392008, 160: 5521384, 161: 5610705, 162: 5739009, 163: 5818390, 164: 5930196, 165: 6052893, 166: 6156139, 167: 6239472, 168: 6402720, 169: 6493681, 170: 6623853, 171: 6741078, 172: 6864016, 173: 6953457, 174: 7094451, 175: 7215016, 176: 7359936, 177: 7475145, 178: 7593865, 179: 7689630, 180: 7886244, 181: 7984165, 182: 8130747, 183: 8253888, 184: 8403448, 185: 8523897, 186: 8684853, 187: 8802826, 188: 8949612, 189: 9105537, 190: 9267595, 191: 9376656, 192: 9574704, 193: 9686065, 194: 9827097, 195: 9997134, 196: 10174780, 197: 10290813, 198: 10493367, 199: 10611772, 200: 10813692}
print(ans[k])
### BUGGY CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) 
N, M = map(int, input().split())
a_list = []
dp = [0]*(N+1)
for _ in range(M):
  a = int(input())
  a_list.append(a)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a_list = set([int(input()) for i in range(M)])
dp = [0]*(N+1)

dp[0] = 1
for i in range(1,N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)
  if i in a_list:
    dp[i] = 0
print(dp[N])
### BUGGY CODE ###

import numpy as np
a, b = (int(i) for i in input().split())
x = range(a, b+1)
y = 0
for z in x:
    y = np.bitwise_xor(y, z)
print(y)


### FIXED CODE ###

a, b = (int(i) for i in input().split())
def f0(x):
    xx = (x + 1) % 4
    if xx == 0:
        return 0
    elif xx == 1:
        return x
    elif xx == 2:
        return 1
    else:
        return x^1
a = f0(a-1)
b = f0(b)
print(a^b)
### BUGGY CODE ###

def cmb2(n):
	result = n * (n - 1) / 2

	return result

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]

	A_set = set(A)

	ans_d = {}
	for a_s in A_set:
		#print(A.count(a))
		ans_d[str(a_s)] = A.count(a_s)

	for a in A:
		#A_new = ans_d.copy()
		ans_d[str(a)] -= 1
		ans = 0
		#print(A_new)
		#print("="*10)
		for a_n in ans_d.values():
			if a_n <= 1:
				continue
			else:
				ans += cmb2(a_n)
		print(int(ans))
		ans_d[str(a)] += 1

### FIXED CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

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

	c = Counter(A)
	s = 0
	for v in c.values():
		s += cmb2(v)

	for a in A:
		print(s - cmb2(c[a]) + cmb2(c[a] - 1))
### BUGGY 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)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline
q = int(input())

p=1000003

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

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

H,W,N=map(int,raw_input().split())
XY=[]
for i in range(N):
    XY.append(map(int,raw_input().split()))

XY.sort()

conditions=[i-1 for i in range(H+1)]
for xy in XY:
    if conditions[xy[0]]>=xy[1]:
        print xy[0]-1
        break
    if xy[1]==conditions[xy[0]]+1:
        conditions=[conditions[i] if i<=xy[0] \
                   else conditions[i]-1 for i in range(H+1)]
 
else:
    print H

### FIXED CODE ###

H,W,N=map(int,raw_input().split())
XY=[]
for i in range(N):
    XY.append(map(int,raw_input().split()))

XY.sort()

conditions=[2,1]
for xy in XY:
    if xy[0]>conditions[0]:
        conditions=[xy[0],conditions[1]+xy[0]-conditions[0]]
    if conditions[1]>=xy[1]:
        print xy[0]-1
        break
    if xy[1]==conditions[1]+1:
        conditions=[conditions[0],conditions[1]-1]
else:
    print H
### BUGGY CODE ###

def main():
	N = int(input())
	A = [0]*N
	MOD = 998244353
	summation = 0

	for i in range(N):
		A[i] = int(input())
		summation += A[i]

	# dp[i][j] represents sum of red is j at i position
	dp = [[0 for _ in range(summation+1)] for _ in range(N)]
	dp[0][0] = 2 # green or blue
	dp[0][A[0]] = 1 # red

	for i in range(1, N):
		for j in range(len(dp[i])):
			dp[i][j] += dp[i-1][j] * 2 % MOD # don't use A[i] for red, i.e. use green or blue
			dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0 # use i red

	# total
	ans = (3 ** N) % MOD
	ceil = summation // 2
	if summation % 2 != 0:
		ceil += 1
	ans -= sum([dp[N-1][r] for r in range(ceil, summation+1)])*3
	ans %= MOD

	if summation %2 == 0:
		# case r = g = S/2
		dp  =[[0 for _ in range(summation//2+1)] for _ in range(N)]
		dp[0][0] = 1 # only blue
		dp[0][A[0]] = 1
		for i in range(1, N):
			for j in range(len(dp[i])):
				dp[i][j] += dp[i-1][j] % MOD
				dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j-A[i] <= len(dp[i]) else 0
		ans += dp[N-1][summation//2]*3
		ans %= MOD

	print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	N = int(input())
	A = [0]*N
	MOD = 998244353
	summation = 0

	for i in range(N):
		A[i] = int(input())
		summation += A[i]

	# dp[i][j] represents sum of red is j at i position
	dp = [[0 for _ in range(summation+1)] for _ in range(N)]
	dp[0][0] = 2 # green or blue
	dp[0][A[0]] = 1 # red

	for i in range(1, N):
		for j in range(len(dp[i])):
			dp[i][j] += dp[i-1][j] * 2 % MOD # don't use A[i] for red, i.e. use green or blue
			dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0 # use i red

	# total
	ans = (3 ** N) % MOD
	ceil = summation // 2
	if summation % 2 != 0:
		ceil += 1
	ans -= sum([dp[N-1][r] for r in range(ceil, summation+1)])*3
	ans %= MOD

	if summation %2 == 0:
		# case r = g = S/2
		dp  =[[0 for _ in range(summation//2+1)] for _ in range(N)]
		dp[0][0] = 1 # only blue
		dp[0][A[0]] = 1
		for i in range(1, N):
			for j in range(len(dp[i])):
				dp[i][j] += dp[i-1][j] % MOD
				dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j-A[i] <= len(dp[i]) else 0
		ans += dp[N-1][summation//2]*3
		ans %= MOD

	print(ans)


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

#!/usr/bin/env python3
S = input().strip()
N = len(S)

mod_count = {0: 1}
SS = S[::-1]
sums = [0]
for i in range(N):
    sums.append((sums[-1] + int(SS[i]) * (10**i)) % 2019)
    mod_count[sums[-1]] = mod_count.get(sums[-1], 0) + 1

print(sum([m * (m - 1) for m in mod_count.values()]) // 2)

### FIXED CODE ###

#!/usr/bin/env python3


def main():
    S = input()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    ssum = 0
    for i, c in enumerate(S[::-1]):
        ssum = (ssum + int(c) * pow(10, i, 2019)) % 2019
        mod_count[ssum] += 1

    print(sum([m * (m - 1) for m in mod_count]) // 2)


if __name__ == "__main__":
    main()