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

#D
n, m = list(map(int, input().split()))
alist = list(map(int, input().split()))
for i in range(m) :
    b, c = list(map(int, input().split()))
    alist += [c] * b
    alist.sort()
    alist = alist[-n:]
print(sum(alist))

### FIXED CODE ###

from operator import itemgetter

n, m = map(int, input().split())
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
bcbc.extend([[1, a] for a in aa])
bcbc.sort(key=itemgetter(1), reverse=True)

count = 0
s = 0
for b, c in bcbc :
    if count + b >= n :
        b = n - count
    count += b
    s += b*c
    if count == n :
        break
print(s)
### BUGGY CODE ###

n=int(input())
S=list(input())
A=[[0]*n for i in range(n)]
for i in range(n-1):
  for j in range(i+1,n):
    if S[i]==S[j]:
      A[i][j]=1
dp=[[0]*(n+1) for i in range(n+1)]#i文字目まで、j文字目までの長さ
for i in range(1,n):
  for j in range(i+1,n+1):
    if A[i-1][j-1]==1:
      if j-i<dp[i-1][j-1]+1:
        dp[i][j]=dp[i-1][j-1]
      else:
        dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n+1):
  for j in range(n+1):
    if dp[i][j]>ans:
      ans=dp[i][j]
print(ans)

### FIXED CODE ###

n=int(input())
S=list(input())
dp=[[0]*(n+1) for i in range(n+1)]#i文字目まで、j文字目までの長さ
for i in range(1,n):
  for j in range(i+1,n+1):
    if S[i-1]==S[j-1]:
      if j-i<dp[i-1][j-1]+1:
        dp[i][j]=dp[i-1][j-1]
      else:
        dp[i][j]=dp[i-1][j-1]+1
ans=0
for i in range(n+1):
  for j in range(n+1):
    if dp[i][j]>ans:
      ans=dp[i][j]
print(ans)
### BUGGY CODE ###

N, X = map(int, input().split())
x = list(map(lambda i: abs(int(i) - X), input().split()))

x_min = min(x)

for i in range(x_min, 0, -1):
    if all([_ % i == 0 for _ in x]):
        print(i)
        break

### FIXED CODE ###

N, X = map(int, input().split())
x = list(map(lambda i: abs(int(i) - X), input().split()))

x_min = min(x)

for i in range(x_min, 0, -1):
    cnt = 0
    for j in x:
        if j % i != 0:
            break
        else:
            cnt += 1
    if cnt == N:
        print(i)
        exit()
### BUGGY CODE ###

MOD = (10 ** 9) + 7

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]

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


### FIXED CODE ###

import gc

MOD = (10 ** 9) + 7

S = input()
N = len(S)

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

dp[0][0] = 1
dp[1][0] = 0
dp[2][0] = 0
dp[3][0] = 0

for i in range(1, N + 1):
    for j in range(4):
        s = S[i - 1]
        m = 3 if s == "?" else 1
        dp[j][i] += m * dp[j][i - 1]
        if j == 1:
            if s == "A" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 2:
            if s == "B" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        elif j == 3:
            if s == "C" or s == "?":
                dp[j][i] += dp[j - 1][i - 1]
        dp[j][i] = dp[j][i] % MOD

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

import sys
sys.setrecursionlimit(10**7)

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

# 木構造をリストで表現する
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

G = [[] for _ in range(N+1)]

for a, b in AB:
    G[a].append(b)
    G[b].append(a)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * (N+1)
for p, x in PX:
    P[p] += x


def dfs(v, parent, point):
    # 現在いる頂点vの親までの値をpointとする
    P[v] += point

    for next_v in G[v]:
        if next_v == parent:
            continue
        dfs(next_v, v, P[v])


dfs(1, 0, 0)

res = ' '.join(map(str, P[1:]))
print(res)

### FIXED CODE ###

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

 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    N0=2**(q+1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted(z)[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

for i in range(m-1,-1,-1):
    for j in range(K+1):
        for k in range(K+1):
            M=max(k-j,-a[i])
            if M>=0:
                dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))
            else:
                dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])


### FIXED CODE ###

S,K=input().split()
K=int(K)
K=min(K,300)
mod=998244353
a=[]
val=0
for i in range(len(S)):
    if S[i]=="0":
        a.append(val)
        val=0
    else:
        val+=1

if val!=0:
    a.append(val)
m=len(a)
K=min(sum(a),K)

dp=[[[0 for i in range(K+1)] for j in range(K+1)] for k in range(m+1)]

for j in range(K+1):
    dp[m][j][j]=1

b=[a[i] for i in range(m)]
c=[a[i] for i in range(m)]
for i in range(1,m):
    b[i]+=b[i-1]
b=[0]+b
for i in range(m-2,-1,-1):
    c[i]+=c[i+1]
for i in range(m-1,-1,-1):
    for j in range(K+1):
        for k in range(min(b[i],K)+1):
            M=max(k-j,-a[i])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(input())

ans = 0

d = ([0, 1], [0, -1], [1, 0], [-1, 0])


def bfs(x, y):
    m = []
    for _ in range(H):
        m.append([-1] * W)

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if dj < 0 or dj >= H or di < 0 or di >= W or m[dj][di] != -1 or S[dj][di] == "#":
                continue
            q.append([dj, di, v+1])
            if maximus < v+1:
                maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

s = input()
for n in range(len(s)):
    if s[n:n+2] == 'BC':
        s = s[:n]+'D'+s[n+2:]
#print(s)
ans = 0
cnta = []
for n in range(len(s)):
    if s[n] == 'A':
        cnta.append(0)
    elif s[n] == 'D':
        cnta = list(map(lambda x: x+1, cnta))
    elif s[n] == 'B' or s[n] == 'C':
        ans += sum(cnta)
        cnta = []

ans += sum(cnta)

print(ans)

### FIXED CODE ###

s = input()
s = s.replace('BC','D')

ans = 0
cnta = 0
for n in range(len(s)):
    if s[n] == 'A':
        cnta += 1
    elif s[n] == 'D':
        ans += cnta
    elif s[n] == 'B' or s[n] == 'C':
        cnta = 0

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

#from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[0 for i in range(W)] for j in range(H)]
    todo = []
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append(x0*W+y0)
    for X in todo:
      x0,y0 = divmod(X,W)
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append(x*W+y)
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans > 0 else -1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import math
q = int(input())
for i in range(q):
  l,r = map(int,input().split())
  dp = [0]*(r+1)
  dp[0] = 1
  dp[1] = 1
  dp[2] = 1
  for j in range(2,int(math.sqrt(r)+1)):
    for k in range(j*2,r+1,j):
      dp[k] = 1
      if k*2-1 <= r+1:
        dp[k*2-1] = 1
  ans = dp[l:r+1].count(0)
  print(ans)
  

### FIXED CODE ###

dp=[1]*(10**5+1)
dp[0],dp[1]=0,0
for i in range(2,10**5+1):
  if dp[i]==0:
    continue
  j=i
  while j+i<=10**5:
    j+=i
    if dp[j]==1:
      dp[j]-=1
      
ni=[0]*(10**5+1)
for i in range(2,10**5+1):
  if dp[i]==1 and dp[(i+1)//2]==1:
    ni[i]=1

ru=[0]*(10**5+1)
for i in range(1,10**5+1):
  ru[i]=ru[i-1]+ni[i]

q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(ru[r]-ru[l-1])
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
    
def bfs(v, N, G, E):
    K = 0
    queue = deque()
    new_color = 1
    used_color = set()
    node2colors = [set() for _ in range(N)]
    queue.append(v)
    while queue:
        q = queue.popleft()
        while G[q]:
            nex = G[q].popleft()
            dif = used_color - node2colors[q]
            if dif:
                usd_c = dif.pop()
                dif.add(usd_c)
                E[(q, nex)][1] = usd_c
                node2colors[q].add(usd_c)
                node2colors[nex].add(usd_c)
            else:
                new_c = new_color
                new_color += 1
                E[(q, nex)][1] = new_c
                node2colors[q].add(new_c)
                node2colors[nex].add(new_c)
                used_color.add(new_c)
                K += 1
            queue.append(nex)
    return K

def main():
    N = int(input())
    G = [deque() for _ in range(N)]
    E = dict() # (a, b) -> [idx, color]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        G[a].append(b)
        E[(a, b)] = [i, 0]
    K = bfs(0, N, G, E)
    # ans_list = [value for value in E.values()]
    print(K)
    for value in E.values():
        print(value[1])
main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
    
def bfs(v, N, G, E):
    visited = [0]*N
    queue = deque()
    K = -1
    node2color = [-1 for _ in range(N)]
    queue.append(v)
    visited[v] = 1
    while queue:
        q = queue.popleft()
        color = 0
        for nex in G[q]:
            if visited[nex]:
                continue
            visited[nex] = 1
            color += 1
            if color == node2color[q]:
                color += 1
            
            node2color[nex] = color
            E[(min(q, nex), max(q, nex))] = color
            queue.append(nex)
        K = max(K, color)
    return K

def main():
    N = int(input())
    G = [deque() for _ in range(N)]
    E = dict() # (a, b) -> [idx, color]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        G[a].append(b)
        G[b].append(a)
        E[(a, b)] = 0
    K = bfs(0, N, G, E)
    # ans_list = [value for value in E.values()]
    print(K)
    for value in E.values():
        print(value)
main()
### BUGGY CODE ###

n = int(input())
s = list(input())
 
cnt = []
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            S = ''.join([s[i], s[j], s[k]])
            cnt.append(S)

print(len(set(cnt)))

### FIXED CODE ###

N = int(input())
S = list(input())
PIN = []
b1 = []
for i in range(N-2):
    b2 = []
    if S[i] in b1:
        continue
    else:
        b1.append(S[i])
    for j in range(i+1, N-1):
        b3 = []
        if S[j] in b2:
            continue
        else:
            b2.append(S[j])
        for k in range(j+1, N):
            if S[k] in b3:
                continue
            else:
                b3.append(S[k])
            cand = S[i] + S[j] + S[k]
            PIN.append(cand)

print(len(set(PIN)))
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
l=sorted(L,reverse=True)
ans=0
for i in range(N):
    c=l[i]
    for j in range(i+1,N):
        b=l[j]
        for k in range(j+1,N):
            a=l[k]
            if a+b>c:
                ans+=1
            else:
                break
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
l=sorted(L)
result=0
for i in range(N-2):
    for j in range(i+1,N-1):
        result+=bisect.bisect_left(l,l[i]+l[j])-j-1
print(result)
### BUGGY CODE ###

from operator import itemgetter

N = int(input())
l = []
for i in range(N):
  a, b = map(int, input().split())
  s = [a-b, a+b]
  l.append(s)

l.sort(key = itemgetter(1))
cnt = 0

for i in range(1, N):
  for j in range(i, -N, -1):
    if l[j-1][0] == - 10 ** 9:
      continue
    if l[i][0] < l[j-1][1]:
        l[i][0] = - 10 ** 9
        l[i][1] = - 10 ** 9
        cnt += 1
    break
print(N-cnt)

### FIXED CODE ###

from operator import itemgetter

N = int(input())
l = []
for i in range(N):
  a, b = map(int, input().split())
  s = [a-b, a+b]
  l.append(s)

l.sort(key = itemgetter(1))
cnt = 0
s = - 10 ** 10
for i in range(N):
  if l[i][0] >= s:
    s = l[i][1]
  else:
    cnt += 1
print(N-cnt)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, K + 1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, K + 1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])
### BUGGY CODE ###

n,m=map(int,input().split())
inf=10**15
dis=[[inf for _ in range(n)]for _ in range(n)]
for i in range(n):
	dis[i][i]=0
node=[]
for i in range(m):
	a,b,c=map(int,input().split())
	dis[a-1][b-1]=c
	dis[b-1][a-1]=c
	node.append((a-1,b-1,c))
for i in range(n):
	for j in range(n):
		for k in range(n):
			dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k])
ans=0
for x in node:
	f=0
	for i in range(n-1):
		if f:
			break
		for j in range(i+1,n):
			if dis[i][j]==dis[i][x[0]]+x[2]+dis[x[1]][j]:
				f=1
				break
			elif dis[i][j]==dis[i][x[1]]+x[2]+dis[x[0]][j]:
				f=1
				break
	if f==0:
		ans+=1
print(ans)

### FIXED CODE ###

def main():
	n,m=map(int,input().split())
	inf=10**15
	dis=[[inf for _ in range(n)]for _ in range(n)]
	for i in range(n):
		dis[i][i]=0
	node=[]
	for i in range(m):
		a,b,c=map(int,input().split())
		dis[a-1][b-1]=c
		dis[b-1][a-1]=c
		node.append((a-1,b-1,c))
	for i in range(n):
		for j in range(n):
			for k in range(n):
				dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k])
	ans=0
	for x in node:
		f=0
		for i in range(n-1):
			if f:
				break
			for j in range(i+1,n):
				if dis[i][j]==dis[i][x[0]]+x[2]+dis[x[1]][j]:
					f=1
					break
				elif dis[i][j]==dis[i][x[1]]+x[2]+dis[x[0]][j]:
					f=1
					break
		if f==0:
			ans+=1
	print(ans)
if __name__ == '__main__':
	main()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc127/tasks/abc127_e

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math

# Calculate count of combination
def combination(n, r):
    if r == 0:
        return 1
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        if a % (i + 1):
            a //= (i + 1)
        else:
            b *= (i + 1)
    return a // b


def main():
    MOD = 10**9 + 7
    N, M, K = map(int, input().split())

    pattern = combination(N * M - 2, K - 2)
    # print(com)
    pattern = pattern % MOD
    # print(com)

    ans = 0

    for dx in range(1, M):
        ans += dx * (M - dx) * pattern * (N * N)
        ans = ans % MOD

    # y
    for dy in range(1, N):
        ans += dy * (N - dy) * pattern * (M * M)
        ans = ans % MOD

    ans = ans % MOD
    print(ans)



if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc127/tasks/abc127_e

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math

# Calculate count of combination
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def combination(n, r):
    if r == 0:
        return 1
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        if a % (i + 1):
            a //= (i + 1)
        else:
            b *= (i + 1)
    return a // b


def main():
    MOD = 10**9 + 7
    N, M, K = map(int, input().split())

    pattern = cmb(N * M - 2, K - 2)
    # print(com)
    pattern = pattern % MOD
    # print(com)

    ans = 0

    for dx in range(1, M):
        ans += dx * (M - dx) * pattern * (N * N)
        ans = ans % MOD

    # y
    for dy in range(1, N):
        ans += dy * (N - dy) * pattern * (M * M)
        ans = ans % MOD

    ans = ans % MOD
    print(ans)


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

from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	trains.sort()	
	frms = [x[0] for x in trains]
	tos = [x[1] for x in trains]

	for query in queries:
		start = bisect_left(frms, query[0])
		ans = len([x for x in tos[start:] if x <= query[1]])
		print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + (cmt[i - 1][j] - cmt[i - 1][j - 1]) + xmt[i][j] 
	
	for query in queries:
		i, j = query
		ans = cmt[j][j] - cmt[i - 1][j] - cmt[j][i - 1] + cmt[i - 1][i - 1]
		print(ans)

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

S = input()

N = len(S)

answer = 0

for start in range(N-3):
    for end in range(start+4,N+1):
        if int(S[start:end]) % 2019 == 0:
            answer += 1

print(answer)

### FIXED CODE ###

S = list(map(int, list(input())))

pops = 0
digi = 1
cnt = [0] * 2019
cnt[0] = 1

while S:
    s = S.pop()

    pops = (pops + s * digi) % 2019
    digi = (10 * digi) % 2019

    cnt[pops] += 1

ans = 0

for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2

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

s = input()
q = int(input())
for _ in range(q):
  query = input()
  if query == "1":
    s = s[::-1]
  else:
    t, f, c = query.split()
    if f == "1":
      s = c + s
    else:
      s = s + c
print(s)

### FIXED CODE ###

s = input()
q = int(input())
b = True
left = []
right = []
for _ in range(q):
  query = input()
  if query == "1":
    b = not(b)
  else:
    t, f, c = query.split()
    if int(f) + b == 2:
      left.append(c)
    else:
      right.append(c)
s = "".join(left)[::-1] + s + "".join(right)
print(s if b else s[::-1])