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

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = [0] * (10 ** 5 * 2 + 10)
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())
### BUGGY CODE ###

n=int(input())
str=input()
s=''
count=0
for i in range(0,n-3):
    for j in range(i+1,n-1):
        s=str[i]
        if str[j] not in s:
            s=str[i]+str[j]
            for k in range(j+1,n):
                if k-j != j-i:
                    if str[k] not in s:
                        count=count+1
print(count)

### FIXED CODE ###

n=int(input())
str=input()
count=str.count("R")*str.count("G")*str.count("B")
count0=0
for i in range(0,n-2):
    for j in range(i+1,int((n+i-1)/2)+1):
        k=2*j-i
        if str[k]!=str[i] and str[k]!=str[j] and str[i]!=str[j]:
            count0=count0+1
print(count-count0)
### BUGGY CODE ###

while True:
    x, y, z = map(int, raw_input().split())
    if x==0 and y==0 and z==0: break
    dp = [[0.0 for col in range(5101)] for row in range(61)]
    m = {}
    for i in range(y+10):
        m[i] = (0,0)
    v = []
    v = map(int, raw_input().split())
    for i in range(z):
        n, e, a = map(int, raw_input().split())
        m[n] = (e, a)
    dp[0][0] = 1.0
    for i in range(y):
        for j in range(5001):
            for k in range(x):
                nx = i + v[k]
                if m[nx][0] == 1:
                    dp[min(y,nx+m[nx][1])][j]+=dp[i][j]/x
                elif m[nx][0]==2:
                    dp[nx][j+m[nx][1]]+=dp[i][j]/x
                elif m[nx][0]==3:
                    dp[nx][max(0,j-m[nx][1])]+=dp[i][j]/x
                else:
                    dp[min(y,nx)][j] += dp[i][j]/x                       
    ans = 0.0
    for i in range(5001):   
        ans += dp[y][i]*i
    print int(ans) 

### FIXED CODE ###

while True:
    x, y, z = map(int, raw_input().split())
    if x==0 and y==0 and z==0: break
    dp = [[0.0 for col in range(5101)] for row in range(61)]
    m = {}
    for i in range(y+10):
        m[i] = (0,0)
    v = []
    v = map(int, raw_input().split())
    for i in range(z):
        n, e, a = map(int, raw_input().split())
        m[n] = (e, a)
    dp[0][0] = 1.0
    for i in range(y):
        for j in range(y*100):
            if dp[i][j] == 0.0: continue
            for k in range(x):
                nx = i + v[k]
                if m[nx][0] == 1:
                    dp[min(y,nx+m[nx][1])][j]+=dp[i][j]/x
                elif m[nx][0]==2:
                    dp[nx][j+m[nx][1]]+=dp[i][j]/x
                elif m[nx][0]==3:
                    dp[nx][max(0,j-m[nx][1])]+=dp[i][j]/x
                else:
                    dp[min(y,nx)][j] += dp[i][j]/x                       
    ans = 0.0
    for i in range(5001):   
        ans += dp[y][i]*i
    print int(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

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

    count = 0
    now = 0
    visited = [now+1]
    l = -1
    while count < N:
        if A[now] in visited:
            l = visited.index(A[now])
            break
        else:
            count += 1
            visited.append(A[now])
            now = A[now]-1
    r = len(visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)])
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

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

    count = 1
    now = 0
    visited = [1]
    set_v = set()
    set_v.add(1)
    l = -1
    while count < N:
        x = A[now]
        if x in set_v:
            l = visited.index(x)
            break
        else:
            count += 1
            visited.append(x)
            set_v.add(x)
            now = x-1
    r = count
    # print(l,r,visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)])

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n - 1):
    if a[i] >= n - 1:
        continue
    for j in range(a[i] + i + 1, n):
        if a[i] + a[j] == j - i:
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
ans = 0
for i, j in enumerate(a):
    if i + j < n:
        dp[i + j] += 1
    if 0 < i - j:
        ans += dp[i - j]
print(ans)
### BUGGY CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


    dp = [INF] * 110000
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            if i >= j:
                dp[i] = min(dp[i] , dp[i-j] + abs(h[i-j]- h[i])) 

    print(dp[n-1])

main() 

### FIXED CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


    dp = [INF] * 110000
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

    print(dp[n-1])

main()
### BUGGY CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()


p = int(p) + 1

n = 1
for i in range(p,1,-1):
    if P % (i**N) == 0:
        n = i
        break
print(n)

### FIXED CODE ###

N, P = map(int, input().split())
p = P**(1/N)
if p % 1 == 0:
    print(int(p))
    exit()

lim = int(p) + 1

dic = {}

def my(N,newP):
    for i in range(2,lim+1):
        while newP % i == 0:
            dic[i] = dic.get(i,0) + 1
            newP = newP // i
        if newP < i or i == lim:
            res = 1
            for j,k in dic.items():
                res *= j**(k//N)
            print(res)
            exit()
my(N,P)
### BUGGY CODE ###

N = input()
N = int(N)
A = input()
array = A.split()
ind = 0
for n in array:
    array[ind] = int(n)
    ind = ind+1

sortedarray = sorted(array)

be = sortedarray[(N//2-1)]
af = sortedarray[N//2]
for flag in array:
    ind = sortedarray.index(flag)
    if ind < N/2:
        print(af)
    else: print(be)


### FIXED CODE ###

N = input()
N = int(N)
A = input()
array = A.split()
ind = 0
for n in array:
    array[ind] = int(n)
    ind = ind+1

sortedarray = sorted(array)

be = sortedarray[(N//2-1)]
af = sortedarray[N//2]
for flag in array:
    if flag <= be:
        print(af)
    else: print(be)
### BUGGY CODE ###

S = input()
N = len(S)

MOD = 10**9+7

dp = []

for i in range(N+1):
  dp.append([0]*13)

dp[0][0] =1

for i in range(1,N+1):
  for j in range(13):
    if S[i-1] == "?":
      for k in range(10):
        dp[i][(j*10+k) % 13] += dp[i-1][j]

    else:
      dp[i][(j*10+int(S[i-1])) % 13] += dp[i-1][j]

print(dp[N][5]%MOD)

### FIXED CODE ###

S = input()
N = len(S)

MOD = 10**9+7

dp = []

for i in range(N+1):
  dp.append([0]*13)

dp[0][0] =1

for i in range(1,N+1):
  for j in range(13):
    if S[i-1] == "?":
      for k in range(10):
        dp[i][(j*10+k) % 13] += dp[i-1][j]

    else:
      dp[i][(j*10+int(S[i-1])) % 13] += dp[i-1][j]
    
  
  for j in range(13):
    dp[i][j] = dp[i][j] %MOD

print(dp[N][5]%MOD)
### BUGGY CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
one_count=[]
count=0
for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if a==1:one_count.append(count)
	count=count+1
	if b==n:bone.append(a)
	count=count+1
	
def cat_snuke():
	for i in one_count:
		for j in bone:
			if l[i+1] == j:
				print("POSSIBLE")
				return 0
	print("IMPOSSIBLE")		
cat_snuke()

### FIXED CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

a,b,c,n=map(int, input().split())
count=0
for i in range(3001):
    for j in range(3001):
        if n-i*a-b*j<0:break
        if (n-i*a-b*j)%c==0:
            count+=1
print(count)

### FIXED CODE ###

a,b,c,n=map(int, input().split())
count=0
for i in range(3001):
    for j in range(3001):
        if n-i*a-b*j<0:break
        if (n-i*a-b*j)%c==0:
            count+=1
print(count)
### BUGGY CODE ###

N = int(input())
D = [int(s) for s in input().split()]

if D[0] != 0 or D.count(0) != 1:
  print(0)
  exit()
  
max_distance = [i+1 for i in range(max(D))]
stock = 1
for i in max_distance:
  count_1 = D.count(i-1)
  count_2 = D.count(i)
  if count_1 == 0 or count_2 == 0:
    stock = 0
    break
  stock *= count_1**count_2

print(stock%998244353)

### FIXED CODE ###

N = int(input())
D = [int(s) for s in input().split()]

maximum = max(D)
max_distance = [i+1 for i in range(maximum)]
count_list = [0 for i in range(maximum+1)]
for i in D:
  count_list[i] += 1
if D[0] != 0 or count_list[0] != 1:
  print(0)
  exit()

stock = 1
for i in max_distance:
  count_1 = count_list[i-1]
  count_2 = count_list[i]
  if count_1 == 0 or count_2 == 0:
    stock = 0
    break
  stock *= count_1**count_2

print(stock%998244353)
### BUGGY CODE ###

N = int(input())
A = []
for n in range(N):
    A.append(int(input()))

max_A = sorted(A)[-1]
second_A = sorted(A)[-2]

for n in range(N):
    if A[n] != max(A):
        print(max(A))
    else:
        print(second_A)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

max_A = sorted(A)[-1]
second_A = sorted(A)[-2]

for n in range(N):
    if A[n] != max_A:
        print(max_A)
    else:
        print(second_A)
### BUGGY CODE ###

#入力値処理
n = int(input())
data = [int(s) for s in input().split()]

ans = 0

for i in range(n-1):
  for j in range(i,n):
    ans = ans +  int(bin(data[i] ^ data[j]),0)
ans = ans % (10 ** 9 + 7)

print(int(ans))

### FIXED CODE ###

#入力値処理
n = int(input())
data = [int(s) for s in input().split()]

bindata = []

for value in data:
  tmp = format(value,'b').zfill(60)  
  bindata.append(tmp)

#各桁の1の個数を格納
numlist = []
for i in range(60):
  numlist.append([row[i] for row in bindata])
#print(numlist)

binnum = [0] * 60
for i in range(60):
  binnum[59-i] = numlist[i].count('1')
#print(binnum)

"""
for rowdata in bindata:
  for j in range(60):
    if rowdata[j] == '1':
      numlist[59-j] += 1
"""
ans = 0

#各桁の1の個数と0の個数の積の和を求める
for i in range(60):
  ans += binnum[i] * (n-binnum[i]) * (2 ** i)
ans = ans % (10**9 + 7)
print(ans)






"""
ans = 0

for i in range(n-1):
  for j in range(i,n):
    ans = ans +  int(bin(data[i] ^ data[j]),0)
ans = ans % (10 ** 9 + 7)

print(int(ans))
"""
### BUGGY CODE ###

N = int(input())
w = 0
h = 0
n = 0
for i in range(1,3501):
    for j in range(i,3501):
        if 4*i*j-N*i-N*j <= 0:
            continue
        if (N*i*j)%(4*i*j-N*i-N*j) == 0:
            w = N*i*j//(4*i*j-N*i-N*j)
            h = i
            n = j
            break
print(h,n,w)


### FIXED CODE ###

import sys
N=int(input())
for h in range(1,3501):
    for n in range(h,3501):
        if 4*n*h-N*h-N*n >0:
            if (N*h*n)%(4*n*h-N*h-N*n)==0:
                w=int((N*h*n)/(4*n*h-N*h-N*n))
                print(h,n,w)
                sys.exit()
### BUGGY CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if u not in s[v]:
        s[v].append(u)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,g,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,st,co
    if min(sss[now][nn],coun) == coun:
        if nn == 0 and st == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.appendleft([x,nn,i,coun])
    else:
        if now == st and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)



### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)
### BUGGY CODE ###

import sys
import re

def check(list, word):
  isMatch = False
  for i in reversed(range(len(list))):
    #match =re.search(word+'*', list[i])
    if word == list[i]:
      isMatch = True    
      list.pop(i)

  return isMatch, list

def calc(list):
  count = 0
  while len(list) > 0:
    ret = check(list, min(list))
    if ret[0] == True:
      count += 1
    list = ret[1]

  return count

N = int(input())
A = sys.stdin.readlines()
#改行コード削除
A = [b.strip() for b in A]

#print(N)
#print(A)
#print(min(A))

#最小文字数の単語から調査
#正規表現として、同じ重複があったらカウントし、リストからその要素を削除
#何種類あるかをカウント
print(calc(A))
  


### FIXED CODE ###

import sys
import re

N = int(input())
A = sys.stdin.readlines()
#改行コード削除
A = [b.strip() for b in A]


print(len(list(set(A))))

#print(N)
#print(A)
#print(min(A))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = [input() for iiii in range(H)]

# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()
check_set = set()
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
            check_set.add((i, j))
# print(dist)


def bfs(check_que, dist, check_set):  # distを編集する関数
    #print("{},{}".format(tate, yoko))
    while check_que:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 > h_prime or h_prime >= H or 0 > w_prime or w_prime >= W:
                continue
            if (h_prime, w_prime) not in check_set:
                dist[h_prime][w_prime] = d + 1
                check_que.append((h_prime, w_prime))
                check_set.add((h_prime, w_prime))

    return d


dis = bfs(check_que, dist, check_set)
# print(dist)
print(dis)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # 迷路の縦、横の長さ
maze = []
for _ in range(H):
    maze.append(input())
# print(maze)
dist = [[-1] * W for iii in range(H)]  # スタートからの距離
check_que = deque()

d = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            dist[i][j] = 0
            check_que.append((i, j))
# print(dist)


def bfs(initial_d):  # distを編集する関数
    dis = 0
    #print("{},{}".format(tate, yoko))
    while len(check_que) != 0:

        h, w = check_que.popleft()
        d = dist[h][w]
        for dh, dw in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            h_prime, w_prime = h + dh, w + dw

            if 0 <= h_prime <= H - 1 and 0 <= w_prime <= W - 1:
                if dist[h_prime][w_prime] == -1:
                    dist[h_prime][w_prime] = d + 1
                    check_que.append((h_prime, w_prime))
                    if d + 1 > dis:
                        dis = d+1
    return dis


dis = bfs(0)
# print(dist)
print(dis)
### BUGGY CODE ###

k,s=map(int,input().split())
print(sum([h+i+j==s for j in range(k+1) for i in range(k+1) for h in range(k+1)]))

### FIXED CODE ###

k,s=map(int,input().split())
print(len([1 for z in range(k+1) for y in range(k+1) if 0<=s-y-z<=k]))
### BUGGY CODE ###

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

score=[]
answer=[]

for i in range(N):
    score.append(K)

for j in range(Q):
    for k in range(N):
        if k+1==A[j]:
            pass
        else:
            score[k]-=1


for m in range(N):
    if score[m]<=0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

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

a=[K-Q]*N

for i in A:
    a[i-1]+=1


for j in a:
    if j>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

N = int(input())
import math

A = 1
count = 0
while A < N:
	B = 1
	while A * B < N:
		B += 1
		count += 1
	A += 1
print(count)


### FIXED CODE ###

N = int(input())
import math

A = 1
count = 0
while A < N:
	B = 1
	while A * B < N:
		B += 1
		count += 1
	A += 1
print(count)
### BUGGY CODE ###

a, b = map(int, input().split())

ans = a
for i in range(a + 1, b + 1):
    ans ^= i

print(ans)

### FIXED CODE ###

def xor_array(n):
    if (n + 1) % 4 == 0:
        return 0
    elif (n + 1) % 2 == 0:
        return 1
    elif n % 4 == 0:
        return n
    else:
        return 1 ^ n


a, b = map(int, input().split())
print(xor_array(a - 1) ^ xor_array(b))
### BUGGY CODE ###

from collections import Counter
from operator import mul
from functools import reduce
from math import factorial


def solve(s):
    n, m = map(int, s.split())
    if m == 1:
        return 1
    divisor = []
    for i in range(2, int(m**0.5) + 1):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    divisor = sorted(list(set(divisor)))

    def search(ded, use, j):
        if ded == 1:
            # print("{} {} {}".format(ded, use, j))
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            # print(base)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // d, use + [d], i + j) for i, d in enumerate(divisor[j:]) if ded % d == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))


### FIXED CODE ###

import math

# import time


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)) + 1)]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b + 1, a + 1):
        i *= _i
    return i // math.factorial(b)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1
# print(primes)

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)
### BUGGY CODE ###

def main():
    N, K = list(map(int, input().split()))
    field = list(map(int, input().split()))

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        tmpList = []
        minCost = -1

        for j in range(1, min(K, i) + 1):
            cost = dpList[i-j] + abs(field[i] - field[i - j])

            if(minCost == -1):
                minCost = cost
            elif minCost > cost:
                minCost = cost

        dpList[i] = minCost

    print(dpList[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = list(map(int, input().split()))
    field = list(map(int, input().split()))

    dpList = [0] * N
    dpList[1] = abs(field[0] - field[1])

    for i in range(2, N):
        tmpList = []
        minCost = -1

        minS = max(0, i - K)

        for dpJ, fJ in zip(dpList[minS:i], field[minS:i]):
            cost = dpJ + abs(field[i] - fJ)

            if(minCost == -1):
                minCost = cost
            elif minCost > cost:
                minCost = cost

        dpList[i] = minCost

    print(dpList[-1])

if __name__ == "__main__":
    main()