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

N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
 
dp = [100000000000]*N
 
dp[0] = 0
dp[1] = abs(h[1]-h[0])
 
for i in range(2,N):
  for num in range(K):
    if num+1<=i:
      A = dp[i-num-1]+abs(h[i]-h[i-num-1])
      if dp[i] >= A:
        dp[i] = A
 
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a.pop(0)
for i in range(n-1):
    ans *= a.pop(0)

if ans <= 10**18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = a[0]
if a[-1] == 0:
    print(0)
else:
    for i in range(1, n):
        ans *= a[i]
        if ans > 10**18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
i=1
b = []
j=0



while i<=n:
    print(a.index(i)+1, end=" ")
    i+=1

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
i=1
b = []
j=0

map = {a[i]:str(i+1) for i in range(n)}
print(" ".join([map[i] for i in range(1, n+1)]))
### BUGGY CODE ###


N = int(input())

i = 1
K = []
while(1):
    k = i * (i+1) // 2
    if i > 10**5:
        break
    K.append(k)
    i+=1
 
if not N in K:
    print ('No')
    exit()
print ('Yes')
S = [[],[]]
i = 0

for n in range(1,N+1):
    S[i] += [n]
    S[-1] += [n]
    i+=1
    if n in K:
        if n==N:
            break
        i = 0
        S.append([])
print(len(S))
for s in S:
    print(str(len(s)) + ' ' + ' '.join(map(str,s)))

    
    



### FIXED CODE ###

#coding:utf-8
import numpy as np
n = int(input())


a = np.ones((2,1)).astype(np.int)
a[-1][-1]+len(a)
i = 1
while(1):
    if len(a)>=500:
        break
    if n==a[-1][-1]:
        print ("Yes")
        print (len(a))
        for line in a:
            print (i," ".join(line.astype(np.str).tolist()))
        exit()
    i+=1
    temp = int((1/2)*i*(i+1))
    add = np.array((list(range(temp-i+1,temp+1))))

    a = np.c_[a,add]
    a = np.r_[a,add.reshape(1,-1)]
print ("No")
### BUGGY CODE ###

N = int(input())

ans = 0

for i in range(N-1):
    ans += i+1

print(ans)


### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = np.array(lr() + [0])
# logNで終了
for _ in range(min(K, 15)):
    next = np.array([0] * (N+1))
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    A = next.cumsum()

print(*A[:-1])


### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])
### BUGGY CODE ###

b=list(map(int,input().split()))
L=[]
l=[]
for i in range(b[0]):
    q=list(map(int,input().split()))           
    L.append(q[0])
    l.append(q[1])
x=0
z=0
y=b[1]    
while y>=0 and not L==[]:
    if L==[]:
        print(x-y*(-1)*w)
        z=1
        break
    else:
        a=L.index(min(L))
        y-=l[a]
        x+=l[a]*L[a]
        z=l[a]*L[a]
        w=L[a]
        l=l[:a]+l[a+1:]
        L=L[:a]+L[a+1:]
print(x-y*(-1)*w)

### FIXED CODE ###

b=list(map(int,input().split()))
LL=[]
for i in range(b[0]):
    LL.append(list(map(int,input().split())))
LL.sort()
x=0
z=0
y=b[1]
i=-1
while y>=0 and not LL==[]:
    i+=1
    if y<=LL[i][1]:
        print(x+LL[i][0]*y)
        break
    else:
        y-=LL[i][1]
        x+=LL[i][1]*LL[i][0]
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)

for i in range(M):
  heapq.heapify(list_A)
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(-sum(list_A))




### FIXED CODE ###

import heapq
N,M = map(int,input().split())
list_A = list(map(lambda x: int(x)*(-1),input().split()))	

#print(list_A)
heapq.heapify(list_A)
for i in range(M):
  
  target = heapq.heappop(list_A)
  #print("after heappop",list_A)
  
  '''負の要素の切り捨て除算は切り捨てがマイナスの方に
  行くため少しだけややこしい。'''
  heapq.heappush(list_A, (-1)*((-target) // 2))  # 要素の挿入
  #print("No.",i,"change finished",list_A)

print(-sum(list_A))
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

from decimal import Decimal

import numpy as np
S = str(input())
N = len(S)
A = np.matrix([[0]*N for _ in range(N)])
for i in range(N):
  if S[i]=='R':
    A[i,i+1] = 1
  else:
    A[i,i-1] = 1

x = np.array([1]*N) * np.linalg.matrix_power(A,10**5)
a = []
for i in range(N):
  a.append(x[0,i])
print(*a)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
ans = [0]*n

left = 0
while left<=n-1:
  R_pos = n-1
  for i in range(left,n):
    if S[i]=='L':
      R_pos = i-1
      L_pos = i
      break
  if R_pos == n-1:
    ans[R_pos] += R_pos-left + 1
    break
  right = n-1
  for j in range(i+1,n):
    if S[j] == 'R':
      right = j-1
      break
  ans[R_pos] += (R_pos-left)//2 + (right-R_pos)//2 + 1
  ans[L_pos] += (L_pos-left)//2 + (right-L_pos)//2 + 1
  if right == n-1:
    break
  left = j

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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()

  a=getPrimeList(n)

  l=[]
  b=len(bin(1<<len(a)))-3
  for i in range(1<<len(a)):
    l.append(str(bin(i))[2:].zfill(b))
  
  ans=inf
  for x in l:
    _a=_b=1
    for i,y in enumerate(list(x)):
      if y=='0':
        _a*=a[i]
      else:
        _b*=a[i]
    ans=min(ans,_a+_b-2)

  return ans

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  ans=inf
  for x in range(1,int(math.sqrt(n))+1):
    if n%x==0:
      ans=min(ans,x+n//x-2)
  return ans

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

import collections

N = int(input())
fact = 1
mod = 10**9 + 7

for i in range(1,N+1):
    fact *= i

s = 0
R = fact
I = fact

soinsu = []
tmp = 1
cnt = 1
ans = 1
while s==0:
    for i in range(2,R+1):

        if I%i==0:
            I=I//i
            if I==1:
                s=1
#            soinsu.append(i)
            if i == tmp:
                cnt += 1
            else:
                ans *= (cnt + 1)
                ans %= mod
                cnt  = 1
                tmp = i
            break

#dic = collections.Counter(soinsu)
# ans = 1
# for v in dic.values():
#     ans *= v + 1
#     ans %= mod


print(ans)


### FIXED CODE ###

N = int(input())
fact = 1
mod = 10**9 + 7

if N == 1:
    print(1)
    exit()

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


for i in range(1,N+1):
    fact *= i

s = 0
R = primes(N)
#print(R)
I = fact

soinsu = []
tmp = 1
cnt = 1
ans = 1
while s==0:
    for i in R:

        if I%i==0:
            I=I//i
            if I==1:
                s=1
#            soinsu.append(i)
            if i == tmp:
                cnt += 1
            else:
                ans *= (cnt + 1)
                ans %= mod
                cnt  = 1
                tmp = i
            break

#dic = collections.Counter(soinsu)
# ans = 1
# for v in dic.values():
#     ans *= v + 1
#     ans %= mod


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

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
def t(s):
  return [[s[i][j] for i in range(len(s))] for j in range(len(s[0]))]
def calc(s):
  res = []
  for v in s:
    v.append('-')
    tmp = []
    nc = ''
    nn = 0
    for c in v:
      if nc == '':
        nc = c
        nn += 1
        continue
      if nc == c:
        nn += 1
        continue
      else:
        if nc == '#':
          tmp = tmp + [0 for _ in range(nn)]
        else:
          tmp = tmp + [nn for _ in range(nn)]
        nc = c
        nn = 1
    res.append(tmp)
  return res

tate = t(calc(t(S)))
yoko = calc(S)
print(max([tate[i][j] + yoko[i][j] - 1 for i in range(h) for j in range(w)]))


### FIXED CODE ###

h, w = map(int, input().split())
S = [input() for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

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

s = 0

for i in range(n-1):
    for j in range(i+1,n):
        s += a[i]*a[j]

print(s % (10**9 + 7))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
sum = 0
ans = 0

for i in range(n):
    sum += a[i]

for i in range(n-1):
    sum -= a[i]
    ans += a[i] * sum

print(ans % (10**9 + 7))
### BUGGY CODE ###

from sys import stdin, stdout
def readLine_int_list():return list(map(int, stdin.readline().split()))
def main():
    n=int(input())
    d=readLine_int_list()
    m=int(input())
    t=readLine_int_list()
    
    set_d = set(d)
    set_t = set(t)
    ans = "YES"
    if len(set_t - set_d) > 0:
        ans = "NO"
    else:
        for i in set_t:
            t_cnt = t.count(i)
            d_cnt = d.count(i)
            if t_cnt - d_cnt > 0:
                ans = "NO"
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin, stdout
from collections import defaultdict
def readLine_int_list():return list(map(int, stdin.readline().split()))
def main():
    d = defaultdict(lambda: 0)
    t = defaultdict(lambda: 0)
    
    n=int(input())
    _d=readLine_int_list()
    for i in _d:
        d[i] += 1
        
    m = int(input())
    _t = readLine_int_list()
    
    for i in _t:
        t[i] += 1
    
    ans = "YES"
    for i in t:
        if i in d:
            if t[i] - d[i] > 0:
                ans = "NO"
                break
        else:
            ans = "NO"
            break
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [[-1 for i in range(2)] for i in range(51)]
dp[50][0] = 0
for i in range(49, -1, -1):
  mask = 1<<i
  ones = 0
  for e in a:
    if e&mask:
      ones+= 1
  for e in a:
    if dp[i+1][0]!=-1:
      if k&mask:
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask*(n-ones))
        dp[i][1] = max(dp[i][1], dp[i+1][0] + mask*ones)
      else:
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask*ones)
    if dp[i+1][1]!=-1:
      dp[i][1] = max(dp[i][1], dp[i+1][1] + mask*max(ones, n-ones))
print(max(dp[0][0], dp[0][1]))

### FIXED CODE ###

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [[-1 for i in range(2)] for i in range(51)]
dp[50][0] = 0
for i in range(49, -1, -1):
  mask = 1<<i
  ones = 0
  for e in a:
    if e&mask:
      ones+= 1
  for e in a:
    if dp[i+1][0]!=-1:
      if k&mask:
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask*(n-ones))
        dp[i][1] = max(dp[i][1], dp[i+1][0] + mask*ones)
      else:
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask*ones)
    if dp[i+1][1]!=-1:
      dp[i][1] = max(dp[i][1], dp[i+1][1] + mask*max(ones, n-ones))
print(max(dp[0][0], dp[0][1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
C = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  C[a-1].append(b-1)
  C[b-1].append(a-1)
dist = [-1]*n
dist[0] = 1
A = [0]*n
F = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  F[p-1] += x
def dfs1(v):
  for nv in C[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      dfs1(nv)
dfs1(0)      
def dfs2(v):
  A[v] += F[v]
  for nv in C[v]:
    if dist[nv] > dist[v]:
      A[nv] += A[v]
      dfs2(nv)
dfs2(0)
print(*A)

### FIXED CODE ###

n, q = map(int, input().split())
C = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  C[a-1].append(b-1)
  C[b-1].append(a-1)
dist = [-1]*n
dist[0] = 1
A = [0]*n
F = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  F[p-1] += x
S = [0]
T = [0]
while S:
  v = S.pop()
  for nv in C[v]:
    if dist[nv] == -1:
      dist[nv] = dist[v] + 1
      S.append(nv)
while T:
  v = T.pop()
  A[v] += F[v]
  for nv in C[v]:
    if dist[nv] > dist[v]:
      A[nv] += A[v]
      T.append(nv)
print(*A)
### BUGGY CODE ###

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


while True:
    #すべてが偶数か確認
    for i in range(N):
        if A[i] % 2 == 0:
            continue
        else:
            break

    if A[i] % 2 == 0:
        A[i] = A[i]/2
        n += 1


print(n)

### FIXED CODE ###

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

while 1:
    #すべてが偶数か確認
    for i in range(N):
        if A[i] % 2 == 0:
            continue
        else:
            F = 1
    
    if F == 1 : break 

    for i in range(N):
        A[i] = A[i]/2
    n += 1


print(n)
### BUGGY CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M


print abc%M


### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

L, R = map(int, input().split(" "))

R = min(R, L + 4038)

i = L
res = 2019
while i < R:
    j = i + 1
    while j <= R:
        res = min(res, i * j % 2019)
        j += 1
    i += 1

print(res)


### FIXED CODE ###

L, R = map(int, input().split(" "))

ans = 2019

R = min(R, L + 2019)
for l in range(L, R):
    for r in range(l + 1, R + 1):
        ans = min(ans, (l * r) % 2019)
print(ans)
### BUGGY CODE ###

H=int(input())
if H==1:
    print(1)
else:
    i=0
    count=1
    while H/2!=1:
        i+=1
        count+=2**i
        H=H/2
    i+=1
    count+=2**i
    print(count)

### FIXED CODE ###

H=int(input())
if H==1:
    print(1)
else:
    i=1
    count=1
    while H//2!=1:
        i*=2
        count+=i
        H=H//2
    i*=2
    count+=i
    print(count)
### BUGGY CODE ###

n,k=map(int,input().split())
s=input()
a=[]
tmp=1
for i in range(len(s)-1):
	if s[i] == s[i+1]:
		tmp+=1
	else:
		a.append(tmp)
		tmp=1
a.append(tmp)
if s[0]=='0':
	m=2*k
else:
	m=2*k+1
t=4*k+1
_max=a[0]
for i in range(len(a)):
	tmp=sum(a[i:i+m])
	if tmp>_max:
		_max=tmp
	m=t-m
print(_max)


### FIXED CODE ###

n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)
if s[-1]=='0':
	m=2*k
else:
	m=2*k+1
t=4*k+1
_max=0
i=len(a)-1
if i- m<0:
	print(n)
else:
	while i-m>=0:
		tmp=a[i]-a[i-m]
		#print('i:{} tmp:{}'.format(i,tmp))
		if tmp>_max:
			_max=tmp
		m=t-m
		i-=1
	if a[i]>_max:
		_max=a[i]
	print(_max)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
mini = n
for i in p:
    if i <= mini:
        ans += 1
        mini = i 
print(ans)
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = map(int, readline().split())

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for j in range(1, k):
            tmp = 0
            for i in range(1, n):
                tmp = (tmp + com(m * i, j) * com(m * (n - i), k - j)) % MOD
            ans = (ans + tmp * j * (k - j)) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = map(int, readline().split())

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    def solve(n, m, k):
        ans = 0
        for d in range(1, n):
            ans = (ans + com(n * m - 2, k - 2) * (m ** 2) * (n - d) * d) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


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

s = input()
n = len(s)

count = 0

for i in range(n-3):
    for j in range(i, n):
        number = int(s[i:j+1])
        if number % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

s=input()
s=s[::-1]
n=len(s)

count=[0]*2019
count[0]=1
num,d=0,1

for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1

ans=0
for i in count:
  ans+=i*(i-1)//2
  
print(ans)
### BUGGY CODE ###

from collections import defaultdict

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

counts = defaultdict(int)
As = map(int, input().split())
for A in As:
    counts[A] += 1

for i in range(M):
    B, C = map(int, input().split())
    keys = sorted(counts.keys())
    key_index = 0
    while B > 0:
        if C <= keys[key_index]:
            break
        replace = min(B, counts[keys[key_index]])
        B -= replace
        counts[keys[key_index]] -= replace
        if counts[keys[key_index]] == 0:
            del counts[keys[key_index]]
        counts[C] += replace
        key_index += 1

total = 0
for n, c in counts.items():
    total += n * c
print(total)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

As = map(int, input().split())
counts = defaultdict(int)
for A in As:
    counts[A] += 1
h = sorted(counts.keys())

for i in range(M):
    B, C = map(int, input().split())

    if C not in counts:
        heapq.heappush(h, C)
    counts[C] += B
    if len(h) > N:
        v = heapq.heappop(h)
        del counts[v]

total_count = 0
total = 0
for k in sorted(h, reverse=True):
    c = counts[k]
    c = min(c, N - total_count)
    total += k * c
    total_count += c
    if total_count > N:
        break
print(total)
### BUGGY CODE ###

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

cnt=0
for i, ai in enumerate(a):
    tmp=0
    for aj in a[i:]:
        if tmp^aj==tmp+aj:
            tmp^=aj            
            cnt+=1
        else:
            break
print(cnt)




### FIXED CODE ###

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

cnt=0
tail=0
sec=0
for head in range(n):
    while(tail<n and sec^a[tail]==sec+a[tail]):
        sec^=a[tail]
        tail+=1
    cnt+=(tail-head)
    sec^=a[head]
print(cnt)
### BUGGY CODE ###

N, X, M = map(int, input().split())
NN = N
li = []
while X not in li and N != 0:
    li.append(X)
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

### FIXED CODE ###

N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    isused[X] = True
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))