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

def main():
    MOD = 998244353

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

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

    for i, x in enumerate(A):
        dp[i + 1][0][0] = dp[i][0][0]
        dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
        dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
        for s in range(S, 0, -1):
            dp[i + 1][s][1] = dp[i][s][1] % MOD
            dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
            if s - x >= 0:
                v = dp[i][s - x][1] + dp[i][s - x][0]
                dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
                dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

    print(dp[N][S][2])


if __name__ == '__main__':
    main()

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             dp[i + 1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD


### FIXED CODE ###

# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


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

cho,N = map(int,input().split())
moji = str(input())
for i in range(int(N)):
    s,g = map(int,input().split())
    cmoji = moji[s-1:g]
    print(cmoji.count('AC'))


### FIXED CODE ###

N,K = map(int,input().split())
moji = str(input())
ans = [0]
for i in range(N-1):
    if moji[i] == "A" and moji[i+1] == "C":
        ans.append(ans[i]+1)
    else:
        ans.append(ans[i])

        
for i in range(K):
    st,sp = map(int,input().split())
    print(ans[sp-1]-ans[st-1])
### BUGGY CODE ###

import math

s = list(input())
q = int(input())

mae = []
usi = []
k = 0
m = 0
for i in range(q):
    a = input().split()
    if(a[0] == '1'):
        k += 1
    if(a[0] == '2'):
        if(k %2 == 0):
            if(a[1] == '1'):
                mae.insert(0,a[2])
            else:
                usi.append(a[2])
        else:
            if(a[1] == '1'):
                usi.append(a[2])
            else:
                mae.insert(0,a[2])

if(k % 2 == 1):
    mae = mae[::-1]
    usi = usi[::-1]
    s = s[::-1]
    s = ''.join(usi+s+mae)
else:
    s = ''.join(mae+s+usi)
print(s)




### FIXED CODE ###

from collections import deque

s = list(input())
q = int(input())

mae = deque()
usi = deque()
k = 0
m = 0
for i in range(q):
    a = input().split()
    if(a[0] == '1'):
        k += 1
    if(a[0] == '2'):
        if(k %2 == 0):
            if(a[1] == '1'):
                mae.appendleft(a[2])
            else:
                usi.append(a[2])
        else:
            if(a[1] == '1'):
                usi.append(a[2])
            else:
                mae.appendleft(a[2])
mae = list(mae)
usi = list(usi)

if(k % 2 == 1):
    mae = mae[::-1]
    usi=usi[::-1]
    s = s[::-1]
    s = ''.join(usi+s+mae)
else:
    s = ''.join(mae+s+usi)
print(s)
### BUGGY CODE ###

N=int(input())

li=[]
l=0
m=0

for i in range(N):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
    l=0
    m=0
  else:
    pass

print(int(min(li)))



### FIXED CODE ###

import math 

N=int(input())

li=[]
l=0
m=0

for i in range(math.floor(math.sqrt(N))):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))
### BUGGY CODE ###

X=int(input())
ans1=0
ans2=0
for a in range(-(10**10),10**10):
    for b in range(-(10**10),10**10):
        if a**5-b**5==X:
            ans1=a
            ans2=b
            break
print(ans1,ans2)

### FIXED CODE ###

X=int(input())
ans1=0
ans2=0
for a in range(-(10**3),10**3):
    for b in range(-(10**3),10**3):
        if a**5-b**5==X:
            ans1=a
            ans2=b
            break
print(ans1,ans2)
### BUGGY CODE ###

N = int(input())
lst = list(map(int,input().split()))
s = 1
for i in range(N):
  s = s*lst[i]
if s>10**18:
  print(-1)
else:
  print(s)

### FIXED CODE ###

N = int(input())
lst = list(map(int,input().split()))
if 0 in lst:
  s = 0
else:
  s = 1
  for x in lst:
    s = s*x
    if s > 10**18:
      s = -1
      break
print(s)
### BUGGY CODE ###

n = int(input())

count = 0
count_list = []
ss = []

for i in range(n):
    s = sorted(input())
    
    for num, match in enumerate(ss):
        if match == s:
            count += count_list[num]
            count_list[num] += 1
            break

    else:
        ss.append(s)
        count_list.append(1)

print(count)

### FIXED CODE ###

from collections import Counter

n = int(input())
s =  Counter("".join(sorted(input())) for i in range(n))

print(sum(map(lambda x : x * (x - 1) // 2, s.values())))
### BUGGY CODE ###

l,r = map(int,input().split())

mod_min = 10000000
chk = 10000000000

for i in range(l,r):
    for j in range(i+1,r+1):
        chk = (i*j)%2019
        if chk < mod_min:
            mod_min = chk

print(mod_min)

### FIXED CODE ###

l,r = map(int,input().split())

chk = 0
flg = 1
i = l
mod_min = 100000

while flg:
    for j in range(i+1,r+1):
        chk = (i*j)%2019
        if chk == 0:
            print(0)
            flg = 0
            break
        elif chk < mod_min:
            mod_min = chk
    i += 1
    if i >= r-1:
        print(mod_min)
        flg = 0
### BUGGY CODE ###

import math
q = int(input())


def isPrime(q):
  if q == 2:
    return True
  if q%2 == 0 or q == 1:
    return False
  j = 3
  while j <= math.sqrt(q):
    if q%j == 0:
      return False
    j += 2
  return True

C = []
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))

primes = []
for i in range(1, 100000):
  if isPrime(i):
    primes.append(i)

for i in range(q):
  count = 0
  for j in primes:
    if j < ran[i][0]:
      continue
    if j > ran[i][1] :
      break
    if ((j+1)//2) in primes:
      count += 1
  C.append(count)

for i in range(q):
  print(C[i])


### FIXED CODE ###

primes = [True]*100000
for i in range(2,100000):
  if primes[i] == False:
    continue
  for j in range(2*i, 100000, i):
    primes[j] = False

c = [0]*100000

for i in range(3,100000):
  if primes[i] and primes[(i+1)//2] == True:
    c[i] = c[i-1]+1
  else:
    c[i] = c[i-1]


q = int(input())
ran = []
for i in range(q):
  ran.append(list(map(int, input().split())))
for i in range(q):
  print(c[ran[i][1]]-c[ran[i][0]-1])
### BUGGY CODE ###

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

exv = list()

for a in p:
    exv.append((1+a)/2)

sm = 0
mx = 0

q = list()

for a in range(N):
    sm += exv[a]
    q.append(exv[a])
    if len(q) > K:
        sm -= q.pop(0)
    if len(q) == K:
        mx = max(mx,sm)

print('{:.12f}'.format(mx))

### FIXED CODE ###

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

from collections import deque

exv = list()

for a in p:
    exv.append((1+a)/2)

sm = 0
mx = 0

q = deque()

for a in range(N):
    sm += exv[a]
    q.appendleft(exv[a])
    if len(q) > K:
        sm -= q.pop()
    if len(q) == K:
        mx = max(mx,sm)

print('{:.12f}'.format(mx))
### BUGGY CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

threshold = sum(a for a, b in AB)
bestA, bestB = max(AB, key=lambda ab: ab[0] / ab[1])

@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    times = (h - threshold) // bestA
    if times > 0:
        return bestB * times + f(h - bestA * times)

    return min(b + f(h - a) for a, b in AB)

print(f(H))


### FIXED CODE ###

import sys
from functools import lru_cache

sys.setrecursionlimit(1000000)

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

AB = []
for i in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

'''
H = 10000
N = 1000
import random
AB = []
for i in range(N):
    A = random.randint(1, 10000)
    B = random.randint(1, 10000)
    AB.append((A, B))
'''




@lru_cache(maxsize=None)
def f(h):
    if h <= 0:
        return 0
    best = float('inf')
    for a, b in AB:
        val = b + f(h - a)
        if val < best:
            best = val
        else:
            break
    return best

AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)
bestA, bestB = AB[0]
threshold = sum(a for a, b in AB)

ans = None
times = (H - threshold) // bestA
if times > 0:
    ans = bestB * times + f(H - bestA * times)
else:
    ans = f(H)

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


def anagram(str1, str2):
    str1List = list(str1)
    str2List = list(str2)

    str1List.sort()
    str2List.sort()

    anagramFlg = 1

    for i in range(len(str1List)):
        if str1List[i] != str2List[i]:
            anagramFlg = 0
            break

    return anagramFlg


n = int(input())

inputList=[]
for i in range(n):
    line = input()
    inputList.append(line)

# print(inputList)

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        if anagram(inputList[i], inputList[j]) == 1:
            cnt += 1

print(cnt)













### FIXED CODE ###


def combinatnion(num, cmb):
    nmrtr = 1
    dnmntr = 1

    for i in range(cmb):
        nmrtr = nmrtr * (num - i)
        dnmntr = dnmntr * (i + 1)

    ans = int(nmrtr/dnmntr)
    return ans

n = int(input())

inputList=[]
for i in range(n):
    line = input()
    inputList.append(line)

# print(inputList)

sortedList = []
dic = {}
for i in range(n):
    tmpList = list(inputList[i])
    tmpList.sort()
    tmpword = "".join(tmpList)

    if tmpword in dic:
        dic[tmpword] = dic[tmpword] + 1
    else:
        dic[tmpword] = 1

    # print(dic)

# print(tmpword)

cnt = 0
for val in dic.values():
    if val != 1:
        cnt += combinatnion(val, 2)

print(cnt)
### BUGGY CODE ###

import sys
from fractions import Fraction

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++




def main():
	n = int(input())
	#b , c = tin()
	al = [Fraction(input()) for _ in range(n)]
	ret = 0
	for i, vi in enumerate(al):
		for vj in al[i+1:]:
			if (vi*vj).denominator==1:
				ret += 1
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
#from fractions import Fraction
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def a(s):
	if s.count('.')==0:
		n2=0
		n5=0
		v = int(s)
	else:
		p = s.index('.')
		n2 = -(len(s) - p - 1)
		n5 = -(len(s) - p - 1)
		if p == 1 and s[0]=='0':
			v= int(s[2:])
		else:
			v = int(s[:p]+s[p+1:])
	while v % 2 == 0:
		v = v//2
		n2+=1
	while v % 5 == 0:
		v = v//5
		n5+=1
	return str(n2)+'_'+str(n5)

def main():
	n = int(input())
	#b , c = tin()
	al = [a(input()) for _ in range(n)]
	cal = collections.Counter(al)
	#pa(cal)
	ret = 0
	pp = set()
	for k in cal:
		for k2 in cal:
			if k+'_'+k2 in pp:
				continue
			#pa((vi*vj)/(10**20))
			if k==k2:
				a2, a5 = map(int, k.split('_'))
				if a2>=0 and a5 >= 0:
					ret += cal[k]*(cal[k]-1)//2
			else:
				a2, a5 = map(int, k.split('_'))
				b2, b5 = map(int, k2.split('_'))
				if a2+b2 >= 0 and a5+b5 >= 0:
					ret += cal[k]*cal[k2]
				
			pp.add(k+'_'+k2)
			pp.add(k2+'_'+k)
			#pa((k,k2,ret))
			
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

from decimal import Decimal

N = int(input())
p = [i for i in map(Decimal, input().split(" "))]

dp = [[Decimal(0)] * (N+1) for _ in range(N+1)]
dp[0][0] = Decimal(1.0)
for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (Decimal(1.0)-p[i])

res = Decimal(0.0)
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))

### FIXED CODE ###

N = int(input())
p = [i for i in map(float, input().split(" "))]

dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1.0
for i in range(N):
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1.0-p[i])

res = 0.0
for i in range(N//2+1, N+1):
    res += dp[N][i]
print("{:.10f}".format(res))
### BUGGY CODE ###

import math
A, B, N = map(int,input().split())
L = []

def floor(x):
  return math.floor(A * x / B) - A * math.floor(x / B)
  
for i in range(N + 1):
  L.append(floor(i))
  
print(max(L))

### FIXED CODE ###

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

def floor(x):
  return (A * x // B) - A * (x // B)

print(floor(min(B - 1, N)))
### BUGGY CODE ###

def main():
  n=int(input())
  s=tuple(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']
  rg=r+g
  ans=0
  R,G=len(r),len(g)
  for i in r:
    for j in g:
      ans+=n-R-G +(-1 if ((i+j)%2==0  and (i+j)/2 in b) else 0) 
      x,y=((i+j)+abs(i-j)*3)/2,((i+j)-abs(i-j)*3)/2
      ans+=-1 if x in b else 0
      ans+=-1 if y in b else 0
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  R,G,B=s.count('R'),s.count('G'),s.count('B')
  ans=R*G*B
  for i in range(n):
    for j in range(i+1,n):
      if 2*j-i>n-1:
        break
      if s[i]!=s[j] and s[j]!=s[2*j-i] and s[2*j-i]!=s[i]:
        ans-=1
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

def gcd_list2(numbers):
    if (numbers[0] == 1 or numbers[1] == 1 or numbers[2] == 1):
        return 1
    return reduce(math.gcd, numbers)
  
def gcd_list3(numbers):
    g = math.gcd(numbers[0], numbers[1])
    return math.gcd(g, numbers[2])

@lru_cache(maxsize=None)
def gc(a, b):
    if (a % b == 0):
        return b
    return(gc(b, a%b))  

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):
#            if (i < j):
#                g = gc(i, j)
#            else:
#                g = gc(j, i)
#            if (g < k):
#                sum += gc(g, k)
#            else:
#                sum += gc(k, g)
            sum += gc(gc(i, j), k)
#            sum += gcd_list3([i, j, k])
print(sum)            

### FIXED CODE ###

import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache

# input = sys.stdin.readline

n = int(input())

gcd_num = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        g = math.gcd(i, j)
        for k in range(1, n+1):
            gcd_num += math.gcd(g, k)
print(gcd_num)
### BUGGY CODE ###

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

count = 0

for i in range(N):
    minimum = min(Ps[:i + 1])
    if minimum == Ps[i]:
        count += 1

print(count)

### FIXED CODE ###

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

count = 0

minimum = Ps[0]

for i in range(N):
    if minimum >= Ps[i]:
        minimum = Ps[i]
        count+=1

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

import sys
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    lake = [['@' for _ in range(W+2)]]

    for _ in range(H):
        c = ['@'] + list(readline().decode('utf-8').strip()) + ['@']
        lake.append(c)
    lake.append(['@' for _ in range(W+2)])

    dist = [[INF] * (W+2) for _ in range(H+2)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(d)
            sys.exit()
        for i in range(4):
            for k in range(1,K+1):
                n_y = y + dy[i] * k
                n_x = x + dx[i] * k

                if lake[n_y][n_x] == '.':
                    if dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

max_gcd = 0
max_gcd_index = -1
for i in range(len(li)):
    tmp = li[:]
    del tmp[i]
    if max_gcd < gcd(*tmp):
        max_gcd = gcd(*tmp)
        max_gcd_index = i

print(max_gcd)

### FIXED CODE ###

from fractions import gcd

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

# 入力が2つなら最大値が解となる
if n == 2:
    print(max(A))
    exit()

# A1 A2 A3の最大公約数はA1とA2の最大公約数とA3の最大公約数と同値になるので、
# 左右から順番に最大公約数を求めていく。
# 初期値を代入する（右からは0番目にAの最初の要素を、左からは末尾にAの末尾の要素）
gcdL = [0]*n
gcdR = [0]*n
gcdL[0] = A[0]
gcdR[-1] = A[-1]

for i in range(1, n):
    gcdL[i] = gcd(gcdL[i-1], A[i])
    gcdR[-i-1] = gcd(gcdR[-i], A[-i-1])

# A0～AiとAi+1～Anの最大公約数を求めていく
# 最大値が解となる
ans = gcdR[1]
for i in range(1, n-1):
    tmp = gcd(gcdL[i-1], gcdR[i+1])
    ans = max(ans, tmp)
ans = max(ans, gcdL[-2])

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
a_sort = sorted([int(i) for i in input().split()])

Min = 0
Max = 0

def SUM(a):
    count = 0
    comb = 1
    for i, num in enumerate(a_sort):
        if i == k-1:
            count += num
        elif i > k-1:
            comb = comb * i // (i-k+1)
            count += (comb * num) % (10**9+7)
            count = count % (10**9+7)
    return int(count)

Max = SUM(a_sort)
Min = SUM(a_sort.reverse())

print((Max - Min + (10**9+7)) % (10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P
 
        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    
 
        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    # nCk (mod P)   (ただし、n<=N)
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P
 
def main():
    N,K = map(int,input().split())
    A = sorted([int(i) for i in input().split()])
 
    mod = 10**9+7
 
    COMB = Combination(N,mod)
 
    cmb = [0] * (N-K+1)
    for i in range(N-K+1):
        cmb[i] = COMB.getComb(i+(K-1),K-1)
 
    sum_max = 0
    for i in range(K-1,N):
        sum_max = (sum_max + cmb[i-(K-1)] * A[i]) % mod
 
    sum_min = 0
    for i in range(N-K,-1,-1):
        sum_min = (sum_min + cmb[(N-K)-i] * A[i]) % mod
 
    answer = sum_max - sum_min
    print(answer % mod)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from sys import stdin as I
from sys import stdout as O
N,K = map(int,I.readline().split())
H = [None] + list(map(int,I.readline().split()))
DP = [1000000000000 for i in range(N+1)]
DP[1] = 0
for i in range(2,N+1): 
	for j in range(1,min(i-1,K)+1):DP[i] = min(DP[i],DP[i-j]+abs(H[i]-H[i-j]))
print(DP[N])

### FIXED CODE ###

from sys import stdin as I
from sys import stdout as O
N,K = map(int,I.readline().split())
H = [None] + list(map(int,I.readline().split()))
DP = [1000000000000 for i in range(N+1)]
DP[1] = 0
for i in range(2,N+1): 
	for j in range(1,min(i-1,K)+1):DP[i] = min(DP[i],DP[i-j]+abs(H[i]-H[i-j]))
print(DP[N])
### BUGGY CODE ###

def sub():
    N, K = map(int, input().split())
    hs = [int(e) for e in input().split()]
    optimal_values = [None for _ in range(N)]
    optimal_values[0] = 0
    for i in range(1, N):
        buf = []
        for j in range(1, K + 1):
            delta = i - j
            if delta >= 0:
                buf.append(optimal_values[delta] + abs(hs[i] - hs[delta]))
            else:
                break

        optimal_values[i] = min(buf)

    print(optimal_values[-1])


sub()


### FIXED CODE ###

def sub():
    INF = 10 ** 12
    N, K = map(int, input().split())
    hs = [int(e) for e in input().split()]
    optimal_values = [INF for _ in range(N)]
    optimal_values[0] = 0
    for i in range(0, N):
        for j in range(1, K + 1):
            p = i + j
            if p < N:
                optimal_values[p] = min(
                    optimal_values[p], optimal_values[i] + abs(hs[p] - hs[i])
                )
            else:
                break
    print(optimal_values[-1])
    # print(optimal_values)


sub()