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

import copy
from collections import defaultdict

n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = {}
x = []
z = [0]
for i in range(n - 1, n - k - 1, -1):
    if sushi[i][0] in t.keys():
        x.append(i)
        t[sushi[i][0]] += 1
    else:
        t[sushi[i][0]] = 1
    z[0] += sushi[i][1]
y = []
yd = list(t.keys())
for i in range(n - k - 1, -1, -1):
    if sushi[i][0] not in yd:
        y.append(i)
        yd.append(sushi[i][0])

for k in range(1, min(len(x), len(y)) + 1):
    xi = x[-k]
    z.append(z[-1] - sushi[xi][1] + sushi[y[k - 1]][1])

ans = 0
p = len(t.keys())
for i in range(len(z)):
    ans = max(ans, z[i] + (p + i) ** 2)
print(ans)


### FIXED CODE ###

import heapq

n, k = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(n)]
sushi.sort(key=lambda x: x[1])
t = {}
x = []
z = 0
for i in range(n - 1, n - k - 1, -1):
    ti, di = sushi[i]
    if ti in t.keys():
        heapq.heappush(x, di)
        t[ti] += 1
    else:
        t[ti] = 1
    z += di

p = len(t.keys())
ans = z + p ** 2
for i in range(n - k - 1, -1, -1):
    if len(x) == 0:
        break
    ti, di = sushi[i]
    if ti not in t.keys():
        t[ti] = 1
        z += di - heapq.heappop(x)
        p += 1
        ans = max(ans, z + p ** 2)

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

"""
3*10**5
単純に両側の差を全探索だと間に合わないO(N*2)

情報を先に保存しておきそれを使う
"""

N = int(input())
S = input()

E_list = [0]
W_list = [0]

n = 0
for i in range(1,N):
    if S[i-1] == "W":
        n += 1
        W_list.append(n)
    else:
        W_list.append(n)

n = 0
for i in reversed(range(N-1)):
    if S[i+1] == "E":
        n += 1
        E_list.insert(0,n)
    else:
        E_list.insert(0,n)

ans = 10*6
for i in range(N):
    ans = min(E_list[i] + W_list[i], ans)

print(ans)

### FIXED CODE ###

"""
3*10**5
単純に両側の差を全探索だと間に合わないO(N*2)

情報を先に保存しておきそれを使う
"""

N = int(input())
S = input()

E_list = [0] * N 
W_list = [0] * N

n = 0
for i in range(1,N):
    if S[i-1] == "W":
        n += 1
        W_list[i] = n
    else:
        W_list[i] = n

n = 0
for i in reversed(range(N-1)):
    if S[i+1] == "E":
        n += 1
        E_list[i] = n
    else:
        E_list[i] = n

print(min([e+w for e,w in zip(E_list, W_list)]))
### BUGGY CODE ###

from itertools import combinations as combi
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)

  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
    
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
N, K, L = map(int, input().split())
k = UnionFind(N)
l = UnionFind(N)
checkset = set()
res = [1] * (N + 1)
for _ in range(K):
  x, y = map(int, input().split())
  k.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for _ in range(L):
  x, y = map(int, input().split())
  l.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for c in combi(list(checkset), 2):
  if k.isSameGroup(c[0], c[1]) and l.isSameGroup(c[0], c[1]):
    res[c[0]] += 1
    res[c[1]] += 1
print(*(res[1: ]))



### FIXED CODE ###

from collections import defaultdict as dd
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)

  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
    
  def Count(self, x):
    return -self.root[self.Find_Root(x)]
N, K, L = map(int, input().split())
k = UnionFind(N)
l = UnionFind(N)
checkset = set()
res = [1] * (N + 1)
roots = dd(int)
for _ in range(K):
  x, y = map(int, input().split())
  k.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for _ in range(L):
  x, y = map(int, input().split())
  l.Unite(x, y)
  checkset.add(x)
  checkset.add(y)
for i in list(checkset):
  kr = k.Find_Root(i)
  lr = l.Find_Root(i)
  roots[(kr, lr)] += 1
#print(roots)
for i in list(checkset):
  kr = k.Find_Root(i)
  lr = l.Find_Root(i)
  res[i] = roots[(kr, lr)]
  
print(*(res[1: ]))
### BUGGY CODE ###

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

max = 0
for n in range(N):
  l = n
  r = n
  sum = 0.5 * (p_list[n]+1)
  len = 1
  while(len < K):
    if(l == 0):
      r += 1
      sum += 0.5 * (p_list[r]+1)
      len += 1
      continue
    if(r == N - 1):
      l += -1
      sum += 0.5 * (p_list[l]+1)
      len += 1
      continue
    if(p_list[l-1] >= p_list[r+1]):
      l += -1
      sum += 0.5 * (p_list[l]+1)
      len += 1
    else:
      r += 1
      sum += 0.5 * (p_list[r]+1)
      len += 1
  if(sum > max):
        max = sum
print(max)

### FIXED CODE ###

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

sum = 0
for k in range(K):
  sum += p_list[k]
max = sum

i = 0
while(i + K  < N):
  sum = sum - p_list[i] + p_list[i+K]
  if(sum > max):
    max = sum
  i += 1

print(0.5 * (max+K))
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
T = [list(map(int, input().split())) for _ in range(Q)]

index = {i for i, X in enumerate(S) if X == 'A'}

for i in range(Q):
  l, r = T[i][0], T[i][1]
  count = 0
  index1 = index & set(range(l-1, r-1))
  for j in index1:
    if S[j+1] =='C':
      count += 1
  print(count)

### FIXED CODE ###

N, Q = list(map(int, input().split()))
S = input()
T = [list(map(int, input().split())) for _ in range(Q)]

total_list = []
total = 0
try:
  for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
      total += 1
    total_list.append(total)

  for i in range(Q):
    l, r = T[i][0], T[i][1]
    if l != 1:
      print(total_list[r-2]-total_list[l-2])
    else:
      print(total_list[r-2])
except IndexError:
  print(0)
### BUGGY CODE ###

n=int(input())
cnt=1
for it in map(int,input().split()):
  cnt*=it
if cnt>1000000000000000000:
  print(-1)
else:
  print(cnt)

### FIXED CODE ###

n=int(input())
cnt=1
a=sorted(list(map(int,input().split())))
for it in a:
  cnt*=it
  if cnt>1000000000000000000:
    print(-1)
    exit()
if cnt>1000000000000000000:
  print(-1)
else:
  print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

#def f(x):
#    if x == 1:
#        return 1
#    else:
#        return f(x-1) + x

[N, K] = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

max_index = 0
max_sum = 0
for i in range(len(P)-(K-1)):
    sum_P = sum(P[i:i+K])
    if sum_P > max_sum:
        max_sum = sum_P
        max_index = i

#print(max_sum)
#print(max_index)

# 隣接したK個のリスト
kk = P[max_index:max_index+K]

# kの期待値を計算
#max_kk = max(kk)
#dp = [0]
#for i in range(1, max_kk+1):
#    dp.append(dp[i-1] + i)
#print(dp)

ans = 0
for k in kk:
    for i in range(1, k+1):
        ans += i/k
        #ans += f(k)/k

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

#def f(x):
#    if x == 1:
#        return 1
#    else:
#        return f(x-1) + x

[N, K] = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

max_index = 0
now_sum = sum(P[:K])
max_sum = now_sum
for i in range(1, len(P)-(K-1)):
    now_sum -= P[i-1]
    now_sum += P[i+K-1]
    #sum_P = sum(P[i:i+K])
    if now_sum > max_sum:
        max_sum = now_sum
        max_index = i

#print(max_sum)
#print(max_index)

# 隣接したK個のリスト
kk = P[max_index:max_index+K]

# kの期待値を計算
max_kk = max(kk)
dp = [0]
for i in range(1, max_kk+1):
    dp.append(dp[i-1] + i)
#print(dp)

ans = 0
for k in kk:
    ans += dp[k]/k

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

# -*- coding utf-8 -*-
import copy

MOD = 10 ** 9 + 7

n = int(input())
uvw_n = [list(map(int, input().split())) for _ in range(n - 1)]

graph = [[-1] * n for _ in range(n)]
for u, v, w in uvw_n:
    graph[u - 1][v - 1] = w
    graph[v - 1][u - 1] = w

root = 0
dist = [-1] * (n)
new = {0}
not_yet = set(list(range(n)))
not_yet -= {0}
while len(new) != 0:
    next_new = set()
    for i in new:
        for j in not_yet:
            if graph[i][j] != -1:
                dist[j] = dist[i] + graph[i][j]
                next_new.add(j)
    not_yet -= next_new
    new = next_new

for d in dist:
    print(d % 2)



### FIXED CODE ###

# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

n = int(input())

graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, w = map(int, input().split())
    graph[u - 1].append((v - 1, w))
    graph[v - 1].append((u - 1, w))

dist = [-1] * n
dist[0] = 0
que = [0]
while len(que) != 0:
    i = que.pop()
    for j, w in graph[i]:
        if dist[j] == -1:
            dist[j] = dist[i] + w
            que.append(j)

for d in dist:
    print(d % 2)
### BUGGY CODE ###

def _solve(current, n, idx, x):
    if n >= len(x) - idx:
        return 0

    if n == 0:
        return x[-1] - current


    if current is None:
        return solve(x[idx], n - 1, idx + 1, x)

    a = x[idx] - current + solve(x[idx], n, idx + 1, x)
    b = solve(x[idx], n - 1, idx + 1, x)
    return min(a, b)

def solve(n, m, x):
    if n >= m:
        return 0

    dp = [[0 for _ in range(n + 1)] for _ in range(m)]
    dp[m-1][0] = x[-1] - x[-2]
    for i in range(1, n + 1):
        dp[m-1][i] = 0

    for idx in reversed(range(m - 1)):
        for i in range(n + 1):
            if i >= m - idx + 1:
                dp[idx][i] = 0
            elif i == 0:
                dp[idx][i] = x[-1] - x[idx-1]
            elif idx == 0:
                dp[idx][i] = dp[idx+1][i-1]
            else:
                a = x[idx] - x[idx - 1] + dp[idx+1][i]
                b = dp[idx+1][i-1]
                dp[idx][i] = min(a, b)

    return dp[0][n]

def main():
    n, m = map(int, input().split())
    x = [int(s) for s in input().split()]
    x.sort()

    print(solve(n, m, x))

main()


### FIXED CODE ###

def solve(n, m, x):
    if n >= m:
        return 0

    y = [x[i + 1] - x[i] for i in range(m - 1)]
    y.sort(reverse=True)

    return x[-1] - x[0] - sum(y[:n-1])

def main():
    n, m = map(int, input().split())
    x = [int(s) for s in input().split()]
    x.sort()

    print(solve(n, m, x))

main()
### BUGGY CODE ###

h,w,k = map(int,input().split())

s = []
isk = []
for l in range(h):
    sl = input()
    isk.append(sl.count("#"))
    s.append(list(sl))
 

pa = [[0,0] for i in range(h)]
for i in range(h-1):
    if isk[i] == 0:
        pa[i+1][0] = pa[i][0] + 1
    if isk[h-1-i] == 0:
        pa[h-1-i-1][1] = pa[h-1-i][1] + 1
 
res = [[] for l in range(h)]       
now = 1
for i in range(h):
    nowk = isk[i]
    nownow = now
    pp = pa[i][0]
    aa = pa[i][1]
    if nowk != 0:
        for j in range(w):
            p = pp
            a = aa
            if s[i][j] == "#" and nowk != 0:
                res[i].append(nownow)
                while p > 0:
                    if len(res[i-p]) < w:
                        res[i-p].append(nownow)
                        p -= 1
                while a > 0:
                    if len(res[i+a]) < w:
                        res[i+a].append(nownow)
                        a -= 1
                now += 1
                nowk -= 1
                if nowk != 0:
                    nownow += 1
            else:
                res[i].append(nownow)
                while p > 0:
                    if len(res[i-p]) < w:
                        res[i-p].append(nownow)
                        p -= 1
                while a > 0:
                    if len(res[i+a]) < w:
                        res[i+a].append(nownow)
                        a -= 1
                
for l in range(h):
    print(" ".join(map(str,res[l])))
                

### FIXED CODE ###

h,w,k = map(int,input().split())

s = []
isk = []
for l in range(h):
    sl = input()
    isk.append(sl.count("#"))
    s.append(list(sl))
 

pa = [[0,0] for i in range(h)]
for i in range(h-1):
    if isk[i] == 0:
        pa[i+1][0] = pa[i][0] + 1
    if isk[h-1-i] == 0:
        pa[h-1-i-1][1] = pa[h-1-i][1] + 1
 
res = [[] for l in range(h)]       
now = 1
for i in range(h):
    nowk = isk[i]
    nownow = now
    p = pa[i][0]
    a = pa[i][1]
    if nowk != 0:
        for j in range(w):
            if s[i][j] == "#" and nowk != 0:
                res[i].append(nownow)
                now += 1
                nowk -= 1
                if nowk != 0:
                    nownow += 1
            else:
                res[i].append(nownow)
        while p > 0:
            res[i-p] = res[i]
            p -= 1
        while a > 0:
            res[i+a] = res[i]
            a -= 1
                
for l in range(h):
    print(" ".join(map(str,res[l])))
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = 0

for i in range(N):
    first_s = S[i]
    for j in range(i+1, N):
        if S[j] != first_s:
            second_s = S[j]
            for k in range(j+1, N):
                if k == 2*j-i:
                    if (S[k] != first_s) and (S[k] != second_s):
                        continue
                if (S[k] != first_s) and (S[k] != second_s):
                    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())

r, g, b = 0, 0, 0
ans = 0
for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

ans += r*g*b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i < N:
            if (S[i] != S[j]) and (S[j] != S[2*j-i]) and (S[i] != S[2*j-i]):
                ans -= 1

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

S=input()
Q=int(input())
for i in range(Q):
    A="".join(input().split())
    if A[0]=="1":
        S=S[::-1]
    else:
        if A[1]=="1":
            S=A[2]+S
        else:
            S+=A[2]
print(S)


### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
rev=False
for i in range(Q):
    A=input().split()
    if A[0]=="1":
        if rev==False:rev=True
        else:rev=False
    else:
        if rev==False:
            if A[1]=="1":
                S.appendleft(A[2])
            else:
                S.append(A[2])
        else:
            if A[1]=="1":
                S.append(A[2])
            else:
                S.appendleft(A[2])
if rev:
    S.reverse()
print(*S,sep="")
### BUGGY CODE ###

x = int(input())
b = (-1)
for i in range(10**8):
    a = i
    if (a-b)*(a**4+(a**3)*b+(a**2)*(b**2)+a*(b**3)+b**4) == x:
        print(a,b)
        break

### FIXED CODE ###

import sys
x = int(input())
a = []
b = []
t = 0
for i in range(-1000,1000):
    t = i**5
    a.append([t,i])
    b.append([t,i])
    
for i in a:
    for j in b:
        if i[0]-j[0] == x:
            print(i[1],j[1])
            sys.exit()
### BUGGY CODE ###

from collections import deque
from heapq import heappop, heappush

N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
Q = int(input())
VDC = [[int(i) for i in input().split()] for _ in range(Q)]
VDC.reverse()

INF = 10 ** 3

color = [-1] * N

def dijkstra(n, d, c):
    dist = [INF] * N
    dist[n] = 0
    que = [(0, n)]

    while que:
        dv, v = heappop(que)
        if dist[v] < dv: continue

        if color[v] < 0: color[v] = c
        if d == dv: continue
        
        for w in edge[v]:
            if dist[w] > dv + 1:
                dist[w] = dv + 1
                heappush(que, (dist[w], w))

def main():
    for v,d,c in VDC:
        dijkstra(v-1, d, c)

    for c in color:
        print(max(c, 0))

if __name__ == "__main__":
    main()

### FIXED CODE ###

# 写経AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
Q = int(input())
VDC = [[int(i) for i in input().split()] for _ in range(Q)]

for i in range(Q):
    VDC[i][0] -= 1

color = [0] * N
# dp[v][d]: 頂点vから距離dは塗装済みか
visited = [[False] * 11 for _ in range(N)]

for v,d,c in reversed(VDC):
    if visited[v][d]: # 既に塗装済み
        continue
    if color[v] == 0:
        color[v] = c
    for dist in range(d + 1):
        # 距離d以下は塗装済み
        visited[v][dist] = True
    
    q = [v]
    for t in range(d - 1, -1, -1):
        qq = []
        for v in q:
            for w in edge[v]:
                if visited[w][t]:
                    continue
                for dist in range(t + 1):
                    visited[w][dist] = True
                if color[w] == 0:
                    color[w] = c
                qq.append(w)
        q = qq

print(*color, sep="\n")
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

def odd_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if i%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//i)%2:
                    r_divisors.append(n//i)
    return r_divisors + l_divisors[::-1]

N = I()
X = str(input())

ans = 0
divisors = odd_divisors(N)
divisors = [2*N//x for x in divisors]
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = ''.join('1' if c=='0' else '0' for c in T)
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

def use_divisors(n):
    l_divisors, r_divisors = [], []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            if (n//i)%2:
                l_divisors.append(i)
            if i != n//i:
                if (n//(n//i))%2:
                    r_divisors.append(n//i)
    return l_divisors + r_divisors[::-1]
 
N = I()
X = str(input())
Xr = ''.join('1' if c=='0' else '0' for c in X)

ans = 0
divisors = use_divisors(2*N)
C = dict.fromkeys(divisors,0)

for d in divisors:
    T = X[:d//2]
    Tr = Xr[:d//2]
    Tc = T+Tr
    count = int(T,2)
    if int(Tc*(N//d)+Tc[:N-d*(N//d)],2) <= int(X,2):
        count += 1
    C[d] = count
    for d1 in divisors:
        if d%d1==0 and d!=d1:
            C[d] -= C[d1]

ans = 0
for d in divisors:
    ans += d*C[d]
    ans %= mod

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

def resolve():
    n = int(input())
    arr = list(input())
    count = n
    for i in range(n):
        c = 0
        left = arr[:i]
        right = arr[i+1:]
        c += left.count('W')
        c += right.count('E')
        count = min(c, count)

    print(count)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    S = list(input())
    min_c = n
    count_e = S.count('E')
    count_w = 0

    for s in S:
        if s == 'E':
            count_e -= 1
        min_c = min(min_c, count_e + count_w)
        if s == 'W':
            count_w += 1

    print(min_c)

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

import sys
from functools import reduce


def input():
    return sys.stdin.readline().strip()


MOD = 998244353





def power(a, n):
    x = 1
    while n:
        if n & 1:
            x = x * a % MOD
        n >>= 1
        a = a * a % MOD
    return x


def main():
    N, M, K = map(int, input().split())
    answer = M * power(M - 1, N - 1)
    nowu = N - 1
    nowd = 1
    now = 1
    for i in range(K):
        now = now * (nowu) // (nowd)
        ans = M * power(M - 1, N - 1 - i - 1) * now
        nowu -= 1
        nowd += 1
        answer += ans
        answer %= MOD
    print(answer % MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


MOD = 998244353


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10 ** 9 + 7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n - r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n + 1):
            fac.append(fac[i - 1] * i % self.mod)
            facinv.append(facinv[i - 1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n + 1)
        modinv[1] = 1
        for i in range(2, n + 1):
            modinv[i] = self.mod - self.mod // i * modinv[self.mod % i] % self.mod
        return modinv


def power(a, n):
    x = 1
    while n:
        if n & 1:
            x = x * a % MOD
        n >>= 1
        a = a * a % MOD
    return x


def main():
    N, M, K = map(int, input().split())
    answer = 0
    combination = Combination(2 * 10 ** 5 + 1, MOD)
    for i in range(K + 1):
        answer += M * power(M - 1, N - i - 1) * combination(N - 1, i) % MOD
    print(answer % MOD)


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

S = input()
T = input()
dp = [["" for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if i == 0 or j == 0: continue
        if S[i-1] == T[j-1]:
            dp[i][j] = dp[i-1][j-1] + S[i-1]
        else:
            if len(dp[i-1][j]) >= len(dp[i][j-1]): 
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
print(dp[len(S)][len(T)])

### FIXED CODE ###

S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 

length = dp[len(S)][len(T)]
LCS = [0]*length
i = len(S)
j = len(T)
while i > 0 and j > 0: 
    if S[i-1] == T[j-1]: 
        LCS[length-1] = S[i-1]
        i-=1
        j-=1
        length-=1
    elif dp[i-1][j] > dp[i][j-1]: 
        i-=1
    else: 
        j-=1
print("".join(LCS))