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

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
from operator import itemgetter

# なんこか入力
n,m = map(int, input().split())


# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x,key=itemgetter(0))
x = sorted(x,key=itemgetter(1), reverse=True)

#x = sorted(z, key=lambda z: -z[1])
y = [0]*m
#print(x)


for i in range(n):
    for j in range(x[i][0]-1,m):
        if y[j] == 0:
            y[j] = x[i][1]
            break
#    print(y)

answer=0
for i in range(m):
    answer += y[i]
print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import heapq
from operator import itemgetter

# なんこか入力
n,m = map(int, input().split())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x,key=itemgetter(1),reverse = True)
x = sorted(x,key=itemgetter(0))

work = []
j = 0
answer = 0
for i in range(1,m+1,1):
    while j < n and x[j][0] == i:
        heapq.heappush(work,-x[j][1])
#        print(work)
        j += 1
    if work:
        answer -= heapq.heappop(work)

print(answer)
### BUGGY CODE ###

n,q=map(int,input().split())
s=str(input())
grid = []
for i in range(q):
    array = list(map(int, input().strip().split()))
    grid.append(array)


for i in range(0,q):
    target = s[grid[i][0]-1:grid[i][1]]
    count = 0
    flag = False
    for j in range(0,len(target)):
        if (flag == False)&(target[j]=="A"):
            flag = True
        elif (flag == True)&(target[j]=="C"):
            count += 1
            flag = False
    print(count)

### FIXED CODE ###

import numpy as np

n,q=map(int,input().split())
s=str(input())

line = np.zeros([n,])
count = 0
for i in range(1,n):
    if (s[i-1:i+1]=="AC"): 
        count += 1
    line[i]=count 
        
for i in range(q):
    l,r = map(int,input().split())
    target = line[r-1] - line[l-1]
    print(int(target))
### BUGGY CODE ###

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

cost = 10**9
y = min(a)
for i in range(n):
    cost_r = 0
    cost_l = 0
    r = a[i:] + a[:i]
    l = list(reversed(a[:i+1])) + list(reversed(a[i+1:]))
    for j in range(n-1):
        if r[j+1] < r[j]:
            cost_r += k - r[j]
            if l[j+1] < l[j]:
                cost_l += k - l[j]
                continue
            cost_l += l[j+1] - l[j]
            continue
        if l[j+1] < l[j]:
            cost_l += k - l[j]
            cost_r += r[j+1] - r[j]
            continue
        cost_r += r[j+1] - r[j]
        cost_l += l[j+1] - l[j]
    #print(cost_r,cost_l)
    #print(r,l)
    cost = min(cost,cost_l,cost_r)
print(cost)

### FIXED CODE ###

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

cost = max(a[0]+k-a[-1],a[-1]-a[-2])
for i in range(1,n-1):
    cost = max(a[i]-a[i-1],a[i+1]-a[i],cost)
print(k-cost)
### BUGGY CODE ###

H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import scipy as np

A = np.array(A, dtype= np.int16)
WK = np.zeros(A.shape, dtype=np.int16)
i = 0
S = H * W
while True:
    if np.sum(A) == S:
        break
    WK = 0+A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A[:,:-1] |= WK[:,1:]
    A[:,1:] |= WK[:,:-1]
    i += 1

print(i)


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

N,M=map(int,input().split())
L=2**N
l=[float("inf")]*L
l[0]=0
r=(1,2,4,8,16,32,64,128,256,512,1024,2048)
for i in range(M):
    s=0
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    for j in c:
        s+=r[j-1]
    for j in range(L):
        l[j|s]=min(l[j|s],l[j]+a)
if l[-1]==float("inf"):
    print(-1)
else:
    print(l[-1])

### FIXED CODE ###

from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])
### BUGGY CODE ###

n,a,b=map(int,input().split())
mod=10**9+7

def nCmMOD(A,B,Mod):
    #a conb b を　Mod で割った余り
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

A=nCmMOD(n,a,mod)
B=nCmMOD(n,b,mod)
#print(A,B)

def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)%mod
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)%mod

An=pow_r(2,n)
print((An-1+mod*2-A-B)%mod)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7

def nCmMOD(A,B,Mod):
    num,den=1,1
    for i in range(B):
        num*=(A-i)
        den*=(i+1)
        num%=Mod
        den%=Mod
    return (num*pow(den,Mod-2,Mod))%Mod

A=nCmMOD(n,a,mod)
B=nCmMOD(n,b,mod)

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
An=power_func(2,n,mod)

print((An-1+mod*2-A-B)%mod)
### BUGGY CODE ###

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

R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i+1)
    elif S[i] == "G":
        G.append(i+1)
    else:
        B.append(i+1)
        
ans = 0
for r in R:
    for g in G:
        for b in B:
            i = min(r, g, b)
            k = max(r, g, b)
            j = r+g+b-i-k
            if j-i != k-j:
                ans += 1

print(ans)

### FIXED CODE ###

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

R = []
G = []
B = []
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    else:
        B.append(i)
        
ans = len(R) * len(G) * len(B)
for i in R:
    for j in G:
        if abs(j-i) % 2 == 1:
            k1 = min(j, i) - abs(j-i)
            k2 = max(j, i) + abs(j-i)
            if k1 >= 0:
                if S[k1] == "B":
                    ans -= 1
            if k2 <= N-1:
                if S[k2] == "B":
                    ans -= 1
        else:
            k1 = min(j, i) - abs(j-i)
            k2 = max(j, i) + abs(j-i)
            k3 = min(j, i) + abs(j-i)//2
            if k1 >= 0:
                if S[k1] == "B":
                    ans -= 1
            if k2 <= N-1:
                if S[k2] == "B":
                    ans -= 1
            if S[k3] == "B":
                ans -= 1
            
print(ans)
### BUGGY CODE ###

#D
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7


def comb(n, x):
    numerator = 1
    for i in range(n, n - x, -1):
        numerator = numerator * i % mod

    denominator = 1
    for j in range(x, 1, -1):
        denominator = denominator * j % mod

    d = denominator ** mod - 2 % mod

    return numerator * d

# #pow
# # def pow(x, n, mod=10e9+7):
# #     ans = 1
# #     while (n > 0):
# #         if bin(n & 1) == bin(1):
# #             ans *= x
# #         x *= x
# #         n = n >> 1
# #     return ans

a = comb(n, a)
b = comb(n, b)

print((2**n %mod - 1 - a - b) % mod)


### FIXED CODE ###

#D
n, a, b = map(int, input().split())
mod = pow(10, 9) + 7

def comb(n, x):
    numerator = 1
    for i in range(n, n - x, -1):
        numerator = numerator * i % mod

    denominator = 1
    for j in range(x, 1, -1):
        denominator = denominator * j % mod

    d = pow(denominator, mod-2, mod)

    return numerator * d

a = comb(n, a)
b = comb(n, b)

print((pow(2, n, mod) - 1 - a - b) % mod)
### BUGGY CODE ###

def remove_01_10(S):
	S = S.replace('10', '')
	S = S.replace('01', '')
	return S	

S = input()
N = len(S)
for i in range(N):
	if len(S) == len(remove_01_10(S)):
		print(N - len(S))
		exit()
	else:
		S = remove_01_10(S)

### FIXED CODE ###

S = list(input())
N = len(S)
num0 = 0
for i in range(N):
	if S[i] == '0':
		num0 = num0 + 1

num1 = 0
for i in range(N):
	if S[i] == '1':
		num1 = num1 + 1
print(N - abs(num0 - num1))
### BUGGY CODE ###

import heapq

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
res = [(a.count(e),e) for e in set(a)]
div=max(0,len(res)-k)
heapq.heapify(res)
ans=0
while div>0:
    ans+=heapq.heappop(res)[0]
    div-=1
print ans


### FIXED CODE ###

import heapq

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())



d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
l=d.values()
div=max(0,len(l)-k)
if div==0:
    print 0
    exit()


heapq.heapify(l)

ans=0
while div>0:
    ans+=heapq.heappop(l)
    div-=1
print ans
### BUGGY CODE ###


H,W,M=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(M)]
h=[0]*H
w=[0]*W
for i in range(M):
    h[l[i][0]-1]+=1
    w[l[i][1]-1]+=1
maxh=max(h)
maxw=max(w)
hlist=[]
wlist=[]
for i in range(H):
    if h[i]==maxh:
        hlist.append(i)
for i in range(W):
    if w[i]==maxw:
        wlist.append(i)
c=0
for i in hlist:
    for j in wlist:
        flag=0
        for k in range(M):
            if (i+1)==l[k][0] and (j+1)==l[k][1]:
                flag=1
                break
        if flag==0:
            print(maxh+maxw)
            c=1
            break
    if c==1:
        break
if c==0:
    print(maxh+maxw-1)

### FIXED CODE ###

H,W,M=map(int,input().split())
l = [ list(map(int,input().split(" "))) for i in range(M)]
h=[0]*H
w=[0]*W
for i in range(M):
    h[l[i][0]-1]+=1
    w[l[i][1]-1]+=1
maxh=max(h)
maxw=max(w)
hlist=[]
wlist=[]
for i in range(H):
    if h[i]==maxh:
        hlist.append(i)
for i in range(W):
    if w[i]==maxw:
        wlist.append(i)
c=0
for i in range(M):
  if h[l[i][0]-1]==maxh and w[l[i][1]-1]==maxw:
    c+=1
if len(hlist)*len(wlist)==c:
  print(maxh+maxw-1)
else:
  print(maxh+maxw)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

n, m = [int(i) for i in input().split(" ")]

par = [i for i in range(0, n + 1)]
d2p = [0 for i in range(0, n + 1)]

def d2r(x):
    global par
    global d2p
    k = x
    s = 0
    while k != par[k]:
        s += d2p[k]
        k = par[k]
    return s

def root(x):
    global par
    global d2p
    #print(par, d2p)
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        s = d2r(x)
        par[x] = r
        d2p[x] = s
        return r


def unite(x, y, d):
    global par
    global d2p
    #print(x, y, d)
    rx = root(x)
    dx = d2r(x)
    ry = root(y)
    dy = d2r(y)
    if rx != ry:
        par[rx] = ry
        d2p[rx] = dy + d - dx
        #print(par, d2p,"noz")
        return True
    else:
        if dx - dy != d:
            #print(rx, ry, dx, dy)
            return False
        else:
            return True

l = [0] * m
r = [0] * m
d = [0] * m

for i in range(0, m):
    l[i], r[i], d[i] = [int(j) for j in input().split(" ")]

f = True
for i in range(0, m):
    if not unite(l[i], r[i], d[i]):
        f = False
        break

if f:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import queue

n, m = [int(i) for i in input().split(" ")]

g = [[] for i in range(0, n + 1)]
v = [0] * (n + 1)
v_asn = [False] * (n + 1)
f = True

for i in range(0, m):
    l, r, d = [int(i) for i in input().split(" ")]
    g[l].append([r, d])
    g[r].append([l, -d])

for i in range(1, n + 1):
    if not v_asn[i]:
        q = queue.Queue()
        v_asn[i] = True
        q.put(i)
        while not q.empty():
            qi = q.get()
            for a in g[qi]:
                if not v_asn[a[0]]:
                    v_asn[a[0]] = True
                    v[a[0]] = v[qi] + a[1]
                    q.put(a[0])
                else:
                    if v[a[0]] != v[qi] + a[1]:
                        f = False
                        break
        if not f:
            break

if f:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys
n, a, b = map(int, input().split())
if a == 0 or n == 0:
    print(0)
    sys.exit()
for i in range(n //(a + b) + 1):
    if (a + b) * i <= n < (a + b) * (i + 1):
        j = i
        break
if n - (a + b) * j >= a:
    print(a * j + a)
    sys.exit()
else:
    print(a * j + n- (a + b)*j )
    sys.exit()

### FIXED CODE ###

import sys
n, a, b = map(int, input().split())
if a == 0 or n == 0:
    print(0)
    sys.exit()
j = n //(a + b)

if n - (a + b) * j >= a:
    print(a * j + a)
    sys.exit()
else:
    print(a * j + n- (a + b)*j )
    sys.exit()
### BUGGY CODE ###

from collections import deque

H,W,K = map(int,input().split())
src = [input() for i in range(H)]
sx = sy = None
for i,row in enumerate(src):
    if 'S' in row:
        sy = i
        sx = row.index('S')

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
visited = [[0]*W for i in range(H)]
visited[sy][sx] = 1
q = deque([(0,sx,sy)])
mindist = H+W
while q:
    d,x,y = q.popleft()
    if d > K: break
    dist = min(x, W-x-1, y, H-y-1)
    mindist = min(dist, mindist)
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if src[ny][nx] == '#': continue
        if visited[ny][nx]: continue
        q.append((d+1,nx,ny))
        visited[ny][nx] = 1

ans = -(-mindist//K) + 1
print(ans)

### FIXED CODE ###

from collections import deque

H,W,K = map(int,input().split())
src = [input() for i in range(H)]
sx = sy = None
for i,row in enumerate(src):
    if 'S' in row:
        sy = i
        sx = row.index('S')

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
visited = [[0]*W for i in range(H)]
visited[sy][sx] = 1
q = deque([(0,sx,sy)])
mindist = H+W
while q:
    d,x,y = q.popleft()
    if d > K: break
    dist = min(x, W-x-1, y, H-y-1)
    mindist = min(dist, mindist)
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if src[ny][nx] == '#': continue
        if visited[ny][nx]: continue
        q.append((d+1,nx,ny))
        visited[ny][nx] = 1

ans = -(-mindist//K) + 1
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
for i in range(1,n+1):
  print(b.count(i))
  b=b[b.count(i):]


### FIXED CODE ###

from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
for i in range(n):
  print(c[i + 1])
### BUGGY CODE ###

#D問題
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
    B, C = map(int, input().split())
    A.extend([C]*B)
A.sort(reverse = True)
print(sum(A[:N]))




### FIXED CODE ###

import heapq as hq
N, M = map(int, input().split())
A = list(map(int,input().split()))
A = [(-i,1) for i in A]
hq.heapify(A)
for i in range(M):
    B, C = map(int, input().split())
    hq.heappush(A,(-C,B))
sum_A = 0
for i in range(N):
    add_num = hq.heappop(A)
    sum_A += add_num[0]*-1
    if add_num[1] > 1:
        hq.heappush(A,(add_num[0],add_num[1]-1))
print(sum_A)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
now=0
l=[1]
ll=[]
for i in range(n*2):
    now=a[now]
    if now not in l:
        l.append(now)
    elif now in l and now not in ll:
        ll.append(now)
    else:
        break
    now-=1
num=len(l)-len(ll)
if k>num:
    k-=num
    k=k%len(ll)
    print(ll[k])
else:
    k=k%len(l)
    print(l[k])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[1]
di={}
di[1]=1
for i in a:
    b=a[l[-1]-1]
    if b in di:
        x=b
        break
    l.append(b)
    di[b]=1
t1=0
for j in l:
    if j==x:
        break
    else:
        t1+=1
t2=len(l)-t1
if k<=t1:
    print(l[k])
else:
    num=(k-t1)%t2
    print(l[t1+num])
### BUGGY CODE ###

import sys
n = int(input())
a = [int(i) for i in sys.stdin]
a.sort()
b = list(set(a))
count=0
for i in range(len(b)):
  if a.count(b[i])%2!=0:
    count+=1
print(count)

    

### FIXED CODE ###

import sys
n = int(input())
a = [int(i) for i in sys.stdin]
a.sort()
dict = {}
for i in range(n):
  if a[i] in dict:
    del dict[a[i]]
  else: 
  	dict[a[i]]=0
print(len(dict))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ls = set(l)
c = [0] *n
for i in range(1,n+1):
  if i in ls:
    c[i-1] = l.count(i)
for i in range(n):
  print(c[i])

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans =[0]*n
for i in l:
  ans[i-1] +=1
for i in ans:
  print(i)
### BUGGY CODE ###

n,t=map(int,input().split())
a=input().split()
for i in range(n):
    a[i]=int(a[i])

from collections import defaultdict
mouke=defaultdict(int)
def calc(a,i):
    x=a[i]
    if i==len(a)-1:return 0
    else:
        nokori=a[i+1:]
        return max(nokori)-x

saidai=0
for i in range(n):
    ans=calc(a,i)
    if saidai<ans:saidai=ans
    mouke[ans]+=1
    
print(mouke[saidai])

### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
saisyo=a[0]
saidai=0
count=0
for i in range(n):
    if a[i]<saisyo:saisyo=a[i]
    else:
        if a[i]-saisyo>saidai:
            saidai=a[i]-saisyo
            count=1
        elif a[i]-saisyo==saidai:
            count+=1
print(count)
### BUGGY CODE ###

while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	
	for i in range(n):
		max_shelf = sum(book[:i+1])
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m: break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		else:
			break
	
	flag = 0
	unit = min(book)
	while 1:
		max_shelf -= unit
		cur_shelf,num = 0,2
		j = i+1
		while j < n:
			if num > m:
				flag = 1
				break
			if cur_shelf + book[j] > max_shelf:
				num += 1
				cur_shelf = 0
			else:
				cur_shelf += book[j]
				j += 1
		if flag == 1: break
	print max_shelf+unit

### FIXED CODE ###

def isStorage(max_shelf):
	i,cur_shelf,num = 0,0,1
	while i < n:
		if num > m:
			return False
		if cur_shelf + book[i] > max_shelf:
			num += 1
			cur_shelf = 0
		else:
			cur_shelf += book[i]
			i += 1
	else:
		return True
			
while 1:
	m,n = map(int,raw_input().split())
	if m==0: break
	book = [int(raw_input()) for i in range(n)]
	max_shelf = len = sum(book)/2
	while len:
		len /= 2
		max_shelf -= len if isStorage(max_shelf) else -len
	max_shelf += 6
	while isStorage(max_shelf-1):
		max_shelf -= 1
	print max_shelf
### BUGGY CODE ###

MOD = 998244353
factorial = [1]
inverse_factorial = [0]


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    for i in range(1, max_n+1):
        f = (factorial[-1]*i)%MOD
        factorial.append(f)
        inv_f = modpow(f, MOD-2)
        inverse_factorial.append(inv_f)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

MOD = 998244353
factorial = None
inverse_factorial = None


def modpow(a, p):
    ans = 1
    while p:
        if p&1 == 1:
            ans = (ans*a)%MOD
        a = (a*a)%MOD
        p >>= 1
    return ans


def nCr(n, r):
    if r == 0 or r == n:
        return 1
    return (((factorial[n]*inverse_factorial[n-r])%MOD)*inverse_factorial[r])%MOD


def init_nCr(max_n):
    global factorial, inverse_factorial
    factorial = [1]*(max_n+1)
    inverse_factorial = [0]*(max_n+1)
    for i in range(1, max_n+1):
        factorial[i] = (factorial[i-1]*i)%MOD
        inverse_factorial[i] = modpow(factorial[i], MOD-2)


init_nCr(2*10**5+1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, K = read_ints()
    answer = 0
    for k in range(0, K+1):
        answer = (answer+M*modpow(M-1, N-1-k)*nCr(N-1, k))%MOD
    return answer


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

INF = 2 * 10 ** 3 + 1

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()

    # True ---- False
    def is_ok_top(mid: int, a: int, b: int):
        # 検索対象の外にあるものは先に弾く(リストのインデックスなんかだとout of rangeするので)
        if mid < 0:
            return True
        elif mid >= N:
            return False
        return L[mid] < L[a] + L[b]

    def binSearch_top(ok: int, ng: int, a: int, b: int):
        #print(ok, ng)              # はじめの2値の状態
        while abs(ok - ng) > 1:     # 終了条件（差が1となり境界を見つけた時)
            mid = (ok + ng) // 2
            if is_ok_top(mid, a, b):
                ok = mid            # midが条件を満たすならmidまではokなのでokの方を真ん中まで持っていく
            else:
                ng = mid            # midが条件を満たさないならmidまではngなのでngの方を真ん中まで持っていく
            #print(ok, ng)          # 半分に切り分ける毎の2値の状態
        return ok    

    count = 0
    for a in range(0, len(L) - 2):
        for b in range(a + 1, len(L) - 1):
            count += binSearch_top(-1, INF, a, b) - b

    print(count)







if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

INF = 2 * 10 ** 3 + 1

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()

    # True ---- False
    def is_ok_top(mid: int, a: int, b: int):
        # 検索対象の外にあるものは先に弾く(リストのインデックスなんかだとout of rangeするので)
        if mid < 0:
            return True
        elif mid >= N:
            return False
        return L[mid] < L[a] + L[b]

    def binSearch_top(ok: int, ng: int, a: int, b: int):
        #print(ok, ng)              # はじめの2値の状態
        while abs(ok - ng) > 1:     # 終了条件（差が1となり境界を見つけた時)
            mid = (ok + ng) // 2
            if is_ok_top(mid, a, b):
                ok = mid            # midが条件を満たすならmidまではokなのでokの方を真ん中まで持っていく
            else:
                ng = mid            # midが条件を満たさないならmidまではngなのでngの方を真ん中まで持っていく
            #print(ok, ng)          # 半分に切り分ける毎の2値の状態
        return ok    

    count = 0
    for a in range(0, len(L) - 2):
        for b in range(a + 1, len(L) - 1):
            count += binSearch_top(-1, INF, a, b) - b

    print(count)







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

a = list(map(int,input().split()))
N = a[0]
K = a[1]
H = list(map(int,input().split()))
H.sort(reverse=True)
ans = 0
if K >= N:
    print(0)
else:
    for i in range(K):
        b = H.pop(0)
    ans = sum(H)
    print(ans)

### FIXED CODE ###

a = list(map(int,input().split()))
N = a[0]
K = a[1]
H = list(map(int,input().split()))
H.sort(reverse=True)
ans = 0
MOD = 10**9 + 7
if K >= N:
    print(0)
else:
    for i in range(K,N):
        ans += H[i]

    print(ans)