Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left

def main():
	N, X = map(int, input().split(" "))
	L = input().split(" ")
	L = [int(s) for s in L]
		
	L.sort()
	tmp = bisect_left(L, X)
	max1 = L[tmp]
	min1 = L[tmp-1]
	
	ans = min(abs(max1-X), abs(X-min1))
	
	print(ans)
		
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left

def gcd(a, b):
	if a > b:
		a, b = b, a
		
	while a > 0:
		a, b = b % a, a
	return b
	
def main():
	N, X = map(int, input().split(" "))
	L = input().split(" ")
	L = [int(s) for s in L]
	
	if N == 1:
		print(abs(L[0]-X))
		sys.exit()
	
	L.sort()
	tmp = bisect_left(L, X)
	
	max1 = 2000000001
	if tmp < len(L):
		max1 = L[tmp]
	
	min1 = 2000000001
	if tmp != 0:
		min1 = L[tmp-1]
	
	seed = 0
	mark = -1
	if abs(max1-X) < abs(X-min1):
		seed = abs(max1-X)
		mark = tmp
	else:
		seed = abs(X-min1)
		mark = tmp-1
	
	ans = 2000000001
	for i, val in enumerate(L):
		if i == mark:
			continue
		tmp = abs(L[i] - L[mark])
		ans_tmp = gcd(tmp, seed)
		if ans > ans_tmp:
			ans = ans_tmp
	
	print(ans)
		
	
if __name__ == "__main__":
	main()
# coding: utf-8
import sys
import math

numbers = []
for line in open('numberset.dat'):
    numbers.append(line.split())

for i in range(len(numbers)):
    sum = int(numbers[i][0]) + int(numbers[i][1])
    print int(math.log10(float(sum))) + 1

### FIXED CODE ###

# coding: utf-8
import sys
import math

numbers = []
for line in sys.stdin:
    numbers.append(line.split())

for i in range(len(numbers)):
    sum = int(numbers[i][0]) + int(numbers[i][1])
    print int(math.log10(float(sum))) + 1
N = int(input())
A = list(map(int, input().split()))
worker_list = [0] * N

for i in range(0, N - 1):
    worker_list[A[i] - 1] += 1

for i in range(N):
    print(worker_list[i])


### FIXED CODE ###

from math import gcd

def gcd_3(a, b, c):
    return gcd(gcd(a, b), c)
sum_gcd = 0
K = int(input())
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for l in range(1, K + 1):
            sum_gcd += gcd_3(i, j, l)

print(sum_gcd)
import math
a=list(map(int,input().split()))
ans=0
if max(a)-min(a)>=2:
    print(0)
else:
    if a[0]==a[1]:
        ans=math.factorial(max(a))
        ans=ans*ans*2
    else:
        ans=math.factorial(max(a))
        ans=ans*ans/max(a)
        #print(ans)

    print(int(ans%1000000007 ))

### FIXED CODE ###

import math
a=list(map(int,input().split()))
ans=0
if max(a)-min(a)>=2:
    print(0)
else:
    if a[0]==a[1]:
        ans=math.factorial(max(a))
        ans=(ans%1000000007)*(ans%1000000007)*2
    else:
        ans=math.factorial(max(a))
        ans1 = math.factorial(min(a))
        ans=(ans%1000000007)*((ans1)%1000000007)
    print(int(ans%1000000007 ))
import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+2):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        s_m += di_m[i]
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)


### FIXED CODE ###

import math
from copy import copy
di = {}
di[0] = 0
for i in range(1, 2*(10**6)+1):
    di[i] = 0
for i in range(1, 2*(10**6)+1):
    count = 0
    for j in range(int(math.log2(i))+4):
        if (i>>j)&1:
            count += 1
    di[i] = di[i%count] + 1
n = int(input())
x = list(input())
x.reverse()
count = 0
for i in x:
    if i =='1':
        count += 1
mod_p = count + 1
mod_m = count - 1
di_p = {}
di_m = {}
for i in range(n):
    di_p[i] = pow(2, i, mod_p)
    if mod_m >= 1:
        di_m[i] = pow(2, i, mod_m)
s_p = 0
s_m = 0
for i in range(n):
    if x[i] == '1':
        s_p += di_p[i]
        if mod_m >= 1:
            s_m += di_m[i]
    else:
        continue
for i in range(n-1, -1, -1):
    sm = copy(s_m)
    sp = copy(s_p)
    if x[i] == '1' and (mod_m == 0 or mod_m == -1):
        print(0)
    elif x[i] == '1':
        sm -= di_m[i]
        sm %= mod_m 
        print(di[sm]+1)
    else:
        sp += di_p[i]
        sp %= mod_p
        print(di[sp]+1)
x=input()
x = x.split()
a = x[0]
b = x[1]

print(a*b,end=' ')
print(a*2+b*2)

### FIXED CODE ###

x=input().split()
a = int(x[0])
b = int(x[1])

print( a*b , a*2+b*2 )
k = int()
s = int(input())
 
if len(s) <= k:
  print(s)
  
else:
  print(s[:k] + "...")

### FIXED CODE ###

k = int(input())
s = input()
 
if len(s) <= k:
  print(s)
  
else:
  print(s[:k] + "...")
A, B = map(double, input().split())
print(int(math.floor(A * B)))

### FIXED CODE ###

A, B = map(str, input().split())

A = int(A)
B = int(''.join(B.split('.')))
print(A * B // 100)
s = input()
l = s[:(len(s)-1)//2:]
r = s[(len(s)+1)//2:]
if a == b and a == a[::-1]:
     print("Yes")
else:
     print("No")

### FIXED CODE ###

s = input()
a = s[:(len(s)-1)//2:]
b = s[(len(s)+1)//2:]
if a == b and a == a[::-1]:
     print("Yes")
else:
     print("No")
n = int(input())

def calc_sum(b, e):
    cnt = (e - b) // b
    return (b + e) * cnt // 2

ans = 0
for i in range(n+1):
    ans += calc_sum(i, n // i * i)

print(ans)

### FIXED CODE ###

n = int(input())

cnt = [1] * (n + 1)
cnt[0] = 0
cnt[1] = 0

p = 2
while p  <= n // 2:
    for i in range(p*2, n+1, p):
        cnt[i] += 1
    p += 1

ans = 0
for i in range(1, n+1):
    # print(i, cnt[i]+1)
    ans += i * (cnt[i] + 1)

print(ans)
a=int(input())
b=int(input())
frag="EQUAL"
if a>b:
  frag="GREATER"
elif a[i]<b[i]:
  frag="LESS"
      
print(frag)

### FIXED CODE ###

a=list(input())
b=list(input())
frag="EQUAL"
if len(a)!=len(b):
  if len(a)>len(b):
    frag="GREATER"
  else:
    frag="LESS"
else:
  for i in range(len(a)):
    if a[i]>b[i]:
      frag="GREATER"
      break
    elif a[i]<b[i]:
      frag="LESS"
      break
      
print(frag)
import sys
import collections

ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
il = list(set(a))
li = collections.Counter(a)
q = ri()
for _ in range(q):
    b, c = rm()
    if b in il:
        if c in il:
            li[c] += li[b]
        else:
            li[c] = li[b]
            il.append(c)
        li[b] = 0
        il.remove(b)
    ans = 0
    for k, v in li.items():
        ans += k*v
    print(ans)



### FIXED CODE ###

import sys
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
t = sum(a)
cnt_li = [0]*10**5
for i in a:
    cnt_li[i-1] += 1

for _ in range(ri()):
    b, c = rm()
    t += (c-b)*cnt_li[b-1]
    print(t)
    cnt_li[c-1] += cnt_li[b-1]
    cnt_li[b-1] = 0
n = int(input())
cheak =[[0]*9 for _ in range]
for i in range(1, n+1):
    s = str(i)
    s1 = int(s[0])-1
    s2 = int(s[-1])-1
    if s2 == 0:
        continue
    cheak[s1][s2] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += cheak[i][j] * cheak[j][i]
print(ans)


### FIXED CODE ###

n = int(input())
cheak_box = [[0]*9 for _ in range(9)]

for i in range(1, n+1):
    s = str(i)
    s1 = int(s[0]) - 1
    s2 = int(s[-1]) - 1
    if s2 == -1:
        continue 
    cheak_box[s1][s2] += 1

ans = 0
for p in range(9):
    for q in range(9):
        ans += cheak_box[p][q] * cheak_box[q][p]
        
print(ans)
N, M = map(int, input().split())
a = set(int(i) for i in input().split())

dp = [0] * (N + 1)
dp[0] = 1

for i in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
a = set(int(input()) for i in range(M))

dp = [0] * (N + 1)
dp[0] = 1

for i in range(1,N+1):
    if i in a:
        dp[i] = 0
        continue
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[N])
a=input()
print a*a*a

### FIXED CODE ###

a=input()
print a*a*a
n = int(input())
x = []
for i in range(n):
  x1,y1=[int(i) for i in input().split()]
  x.append([x1,y1])
ki = (abs(x[0][0]) + abs(x[0][1])) %2
for i in range(n):
  if ki != (abs(x[i][0]) + abs(x[i][1]))%2:
    print(-1)
    exit()
if ki == 1:
  m = 19
  d = [1]*19
else:
  m = 20
  d = [1]*20
ans = []
for i in range(n):
  tmp = ""
  if x[i][0] > 0:
    tmp += "R"*x[i][0]
  else:
    tmp += "L"*abs(x[i][0])
  if x[i][1] > 0:
    tmp += "U"*x[i][1]
  else:
    tmp += "D"*abs(x[i][1])
  while len(tmp) < m:
    tmp += "RL"
  ans.append(tmp)
print(m)
print(*d)
for i in ans:
  print(i)

### FIXED CODE ###

k=int(input())
g = []
i = 0
while k >3:
  if k%2 == 1:
    g.append([1,20-i,(k-1)*2**i])
    k = k//2
    g.append([20-i-1,20-i,0])
    g.append([20-i-1,20-i,1*2**i])
    i+=1
  else:
    k = k//2
    g.append([20-i-1,20-i,0])
    g.append([20-i-1,20-i,1*2**i])
    i+=1
if k==3:
  g.append([1,20-i,(k-1)*2**i])
  k = k//2
  g.append([20-i-1,20-i,0])
  g.append([20-i-1,20-i,1*2**i])
  if 20-i-1 != 1:
    g.append([1,20-i-1,0])
elif k == 2:
  g.append([20-i-1,20-i,0])
  g.append([20-i-1,20-i,1*2**i])
  if 20-i-1 != 1:
    g.append([1,20-i-1,0])
print(20,len(g))
for x,y,z in g:
  print(x,y,z)
memo = [0] * 100000000
memo[1] = 1

def saiki(n):
    global memo
    tmp = 0
    if n <= 1:
        return memo[1]
    else:
        tmp = int(n/2)
        if memo[tmp] == 0:
            memo[tmp] = saiki(tmp)
        return memo[tmp]+memo[tmp]+1
    
h = int(input())
print(saiki(h))


### FIXED CODE ###

#memo = [0] * 100000000
#memo[1] = 1

def saiki(n):
#    global memo
    tmp = 0
    if n <= 1:
        return 1
#        return memo[1]
    else:
        tmp = int(n/2)
        return saiki(tmp) * 2 + 1
#        if memo[tmp] == 0:
#            memo[tmp] = saiki(tmp)
#        return memo[tmp]+memo[tmp]+1
    
h = int(input())
print(saiki(h))
import bisect
a,b,q=map(int,input())
inf=10**18
s=[-inf]+[int(input()) for _ in range(a)]+[inf]
t=[-inf]+[int(input()) for _ in range(b)]+[inf]
for _ in range(q):
  x=int(input())
  b,d=bisect_right(s,x),bisect_right(t,x)
  res=inf
  for i in [s[b-1],s[b]]:
    for j in [t[d-1],s[d]]:
      d1,d2=abs(i-x)+abs(i-j),abs(j-x)+abs(j-i)
      res=min(res,d1,d2)
  print(res)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF=10**18
s=[-INF] + [int(input()) for i in range(A)] + [INF]
t=[-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
#copy code.
# B
import itertools

R, G, B, N = [int(x) for x in input().split()]
RGB = sorted([R, G, B], reverse=True)

cnt = 0
for i in range(N//RGB[0]+1):
    for j in range(N//RGB[1]+1):
        rem = N - (RGB[0]*i) - (RGB[1]*j)
        if rem >= 0:
            num = rem // RGB[2]
            if rem == 0 or rem % (RGB[2]*num) == 0:
                cnt += 1
print(cnt)

### FIXED CODE ###

#  B
import itertools

R, G, B, N = [int(x) for x in input().split()]
RGB = [R, G, B]

cnt = 0
for i in range(N//R+1):
    g_range = (N - RGB[0]*i)//RGB[1]
    for j in range((N-R*i)//G+1):
        if R*i + G*j > N:
            continue
        rem = N - R*i - G*j
        if rem % B == 0: 
            cnt += 1
print(cnt)
from statistics import median

task=[0,0,0]

for i in range(3):
    a=input()
    task[i]=int(a)
    
b=median(task)
sum=0

for i in range(3):
    sum+=abs(b-task[i])
    
sum

### FIXED CODE ###

from statistics import median

task=[int(i) for i in input().split()]
    
b=median(task)
sum=0

for i in range(3):
    sum+=abs(b-task[i])
    
print(sum)
import string as st
string=[]
while True:
    s = input()
    if s == '':
        break
    string.append(s)
    string=','.join(string)
    string = string.lower()
for i in range(len(st.ascii_lowercase)):
    print("{} : {}".format(st.ascii_lowercase[i],string.count(st.ascii_lowercase[i])))


### FIXED CODE ###

import string as st
string=[]
try:
    while True:
        s = input()#入力
        string =list(string)#list変換
        if not s :#空入力のときループぬける
            break
        string.extend(s)#list追加
        string=map(str,string)
        string="".join(string).lower()#str型変換と小文字
except EOFError:
    for i in range(len(st.ascii_lowercase)):
        print("{} : {}".format(st.ascii_lowercase[i],string.count(st.ascii_lowercase[i])))
N = int(input())
string1 = str(input())
string2 = str(input())
res = ''
j = 0
k = 0
for i in range((2*N)):
	if(i%2!=0):
		res+=string1[j]
		j+=1
	else:
		res+=string2[k]
		k+=1
print(res)

### FIXED CODE ###

N = int(input())
string1 , string2 = map(str,input().split())
res = ''
j = 0
k = 0
for i in range((2*N)):
	if(i%2==0):
		res+=string1[j]
		j+=1
	else:
		res+=string2[k]
		k+=1
print(res)
from collections import deque
n,k=[int(i) for i in input().split()]
D=deque()
h=[int(i) for i in input().split()]
for i in h:
    D.append(i)
Dcopy=D.copy()    

### FIXED CODE ###

#デックをインポート
from collections import deque

#前準備
n,k=[int(i) for i in input().split()]

#デックを用意
D=deque()
h=[int(i) for i in input().split()]
for i in h:
    D.append(i)   
    
#答え
maxnum=0

#繰り返す単位
times=min(n,k)

#aとbの操作の合計のlimitを設定
for limit in range(times+1):
#     print(D)
    
    #aの操作を決定
    for a in range(limit+1):
        get=[]
        Dcopy=deque()
        for i in range(n):
            Dcopy.append(D[i])
        b=limit-a
        for i in range(a):
            get.append(Dcopy.popleft())
        for i in range(b):
            get.append(Dcopy.pop())
        get.sort(reverse=True)
#         print(get)
        for i in range(k-limit):
            if len(get)==0:
                break
            if get[-1]>=0:
                break
            get.pop()
        sumnum=0
        for i in get:
            sumnum+=i
        if sumnum>maxnum:
            maxnum=sumnum
            
#         print(a,b,Dcopy,get,sumnum)
print(maxnum)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def lcm(a, b):
    return int(a * b / gcd(max(a, b), min(a, b)))


N = int(input())
T = [int(input()) for i in range(N)]
if N == 1:
    print(T[0])
    exit()
A = T[0]
for i in range(1, N):
    A = lcm(A, T[i])
print(A)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(max(a, b), min(a, b))


N = int(input())
T = [int(input()) for i in range(N)]

A = T[0]
for i in range(N):
    A = lcm(A, T[i])
print(A)
import math

t = input()
n = int(t)
moji_list = {1:"a",2:"b",3:"c",4:"d",5:"e",6:"f",7:"g",8:"h",9:"i",10:"j",11:"k",12:"l",13:"m",14:"n",15:"o",16:"p",17:"q",18:"r",19:"s",20:"t",21:"u",22:"v",23:"w",24:"x",25:"y",26:"z"}
print_list =[]

def hantei(n):
    global print_list

    if 1 <= n and n <= 1000000000000001:
        while(n >= 1):
            s = n % 26
            print_list.insert(0, moji_list[s])
            n = math.floor(n / 26)
    else:
        return

hantei(n)
pu = ''.join(print_list)
print(pu)

### FIXED CODE ###

import math

t = input()
moji_list = {1:"a",2:"b",3:"c",4:"d",5:"e",6:"f",7:"g",8:"h",9:"i",10:"j",11:"k",12:"l",13:"m",14:"n",15:"o",16:"p",17:"q",18:"r",19:"s",20:"t",21:"u",22:"v",23:"w",24:"x",25:"y",26:"z"}
print_list =[]

def hantei(t):
    global print_list
    try:
        int(t)
    except ValueError:
        return
    else:
        n = int(t)
    
    if 1 <= n and n <= 1000000000000001:
        while(n >= 1):
            s = n % 26
            if s == 0:
                s = 26
            print_list.insert(0, moji_list[s])
            n = math.floor(n / 26)
            if s == 26:
                n -= 1
    else:
        return

hantei(t)
pu = ''.join(print_list)
print(pu)
import math

x, y = map(int, input().split())
print((x * y) // math.gcd(x, y))


### FIXED CODE ###

import fractions

x, y = map(int, input().split())
print((x * y) // fractions.gcd(x, y))
from itertools import product
from collections import defaultdict


def main():
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]

    m_list = defaultdict(list)

    for i in range(1, m+1):
        m_list[i].append(0)

    for data in abcd:
        for i in range(1, m+1):
            for j in range(i+1, m+1):
                if j - i == data[2]:
                    if m_list[data[0]][0] == 0:
                        m_list[data[0]] = [i]
                    else:
                        m_list[data[0]].append(i)
                    if m_list[data[1]][0] == 0:
                        m_list[data[1]] = [j]
                    else:
                        m_list[data[1]].append(j)

    ll = list(product(*m_list.values()))

    ans = 0
    for l in ll:
        tmp = 0
        for data in abcd:
            if l[data[1]-1] - l[data[0]-1] == data[2]:
                tmp += data[3]
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from itertools import combinations_with_replacement
from collections import defaultdict


def main():
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]

    ll = list(combinations_with_replacement(range(1, m+1), n))

    ans = 0
    for l in ll:
        tmp = 0
        for data in abcd:
            if l[data[1]-1] - l[data[0]-1] == data[2]:
                tmp += data[3]
        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()
a,b=map(int,input().split())
3 5
print(a*b,2*a+2*b)
 

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
n,k=map(int,input().split())
if k=1:
 print("0")
else:
	print(n-k) 

### FIXED CODE ###

n,k=map(int,input().split())
if k==1:
	print("0")
else:
	print(n-k)
from numpy import sqrt
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
fac = factorization(n)
s = 0
for i in fac:
    s += (-1+sqrt(1+4*i[1]*2))//2
print(int(s))

### FIXED CODE ###

from math import sqrt
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
fac = factorization(n)
s = 0
for i in fac:
    if i[0] != 1:
        s += (-1+sqrt(1+4*i[1]*2))//2
print(int(s))
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def comb_mod(n, r):
    res = 1
    r = min(n - r, r)

    for i in range(r):
        res *= (n - i)
        res %= MOD
        res *= pow((r - i), -1, MOD)

    return res


def main():
    n, m, k = list(map(int, readline().split()))

    com = comb_mod(n * m - 2, k - 2)
    x = 0
    y = 0

    for i in range(n):
        right = n - 1 - i
        x += (right + 1) * right // 2
        x %= MOD

    for i in range(m):
        down = m - 1 - i
        y += (down + 1) * down // 2
        y %= MOD

    ans = 0
    ans += m ** 2 * x * com
    ans += n ** 2 * y * com
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def comb_mod(n, r):
    res = 1
    r = min(n - r, r)

    for i in range(r):
        res *= (n - i)
        res %= MOD
        res *= pow((r - i), MOD - 2, MOD)

    return res


def main():
    n, m, k = list(map(int, readline().split()))

    com = comb_mod(n * m - 2, k - 2)
    x = 0
    y = 0

    for i in range(n):
        right = n - 1 - i
        x += (right + 1) * right // 2
        x %= MOD

    for i in range(m):
        down = m - 1 - i
        y += (down + 1) * down // 2
        y %= MOD

    ans = 0
    ans += m ** 2 * x * com
    ans += n ** 2 * y * com
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()
N, Q = map(int, input().split(" "))
 
ns= [list(map(int, input().split(" ")))  for _ in range(N-1)]
 
flags = [False]*N
dic = [[] for _ in range(N)]
rlt = [0]*N
 
for i in range(N-1):
  dic[ns[i][1]-1] += [ns[i][0]-1]
  dic[ns[i][0]-1] += [ns[i][1]-1]
  
for p, x in (map(int, input().split()) for _ in range(Q)):
  rlt[p - 1] += x
 
que = [0]
while len(que):
  a = que.pop(0)
  flags[a] = True
  for e in dic[a]:
    if flags[e]:
      continue
    else:
      rlt[e] += rlt[a]
      que.append(e)
    
print(" ".join(map(str, rlt)))

### FIXED CODE ###

a = int(input())
s = input()

if a < 3200:
  print('red')
else:
  print(s)
K = input()
D = int(input())
N = len(K)
dp = [[0] * D for i in range(N)]
for i in range(int(K[0])):
    dp[0][i%D] += 1
tight = int(K[0])%D
for i in range(1, N):
    for j in range(D):
        for k in range(10):
            dp[i][j] += dp[i-1][(j-k)%D]
            dp[i][j] %= mod
    for k in range(int(K[i])):
        dp[i][(tight+k)%D] += 1
    tight = (tight+int(K[i]))%D
print((dp[N-1][0]+(tight==0)-1)%mod)

### FIXED CODE ###

mod = 10**9+7
K = input()
D = int(input())
N = len(K)
dp = [[0] * D for i in range(N)]
for i in range(int(K[0])):
    dp[0][i%D] += 1
tight = int(K[0])%D
for i in range(1, N):
    for j in range(D):
        for k in range(10):
            dp[i][j] += dp[i-1][(j-k)%D]
            dp[i][j] %= mod
    for k in range(int(K[i])):
        dp[i][(tight+k)%D] += 1
    tight = (tight+int(K[i]))%D
print((dp[N-1][0]+(tight==0)-1)%mod)