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

# coding: utf-8

# import numpy as np

"""
20191120
D問題のコピペ
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

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

    for n in range(N):
        for w in range(W+1):
            if w >= ws[n]:
                dp[n][w] = max(dp[n-1][w-ws[n]]+vs[n], dp[n-1][w])  # use or not use
            else:
                dp[n][w] = dp[n-1][w]  # not use

    return max(dp[-1])


if __name__ == "__main__":
    print(main())

### FIXED CODE ###

# coding: utf-8

"""
20191120
93分
test:
6 8
2 3
1 2
3 6
2 1
1 3
5 85
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())
    V = sum(vs)

    # initialize
    dp = [[None for _ in range(V+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    dp[0][vs[0]] = ws[0]
    existance[0].add(vs[0])

    for n in range(N-1):
        for v in existance[n]:
            # not-use-update
            if dp[n+1][v] is None:
                dp[n+1][v] = dp[n][v]
            else:
                dp[n+1][v] = min(dp[n][v], dp[n+1][v])
            existance[n+1].add(v)

            # use-update
            if dp[n+1][v+vs[n+1]] is None:
                if dp[n][v] + ws[n+1] <= W:
                    dp[n+1][v+vs[n+1]] = dp[n][v] + ws[n+1]
                    existance[n+1].add(v+vs[n+1])
            else:
                dp[n+1][v+vs[n+1]] = min(dp[n][v] + ws[n+1], dp[n+1][v+vs[n+1]])
                # existance[n+1].add(v+vs[n+1])

    ans = 0
    for v in range(V, 0, -1):
        if dp[-1][v] is not None:
            ans = v
            break

    return ans


def miss_main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


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

n = int(input())
print(sum(range(n)))

### FIXED CODE ###

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

n,a,b = map(int,input().split())
l = []
while True:
    for _ in range(a):
        l.append("r")
    for _ in range(b):
        l.append("b")

    if len(l) >= n:
        print(l[0:n].count("r"))
        exit ()

### FIXED CODE ###

n,a,b = map(int,input().split())
x = -(-n//(a+b))
total = (a+b)*(x-1)
total_a = a*(x-1)
if n - total >= a:
    print (total_a + a)
else:
    print (total_a + (n-total))
### BUGGY CODE ###

from math import *
from collections import defaultdict

MAX_Ai = 10**6
MAX_PRIME = ceil(sqrt(MAX_Ai))
MODE = 10**9+7

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


def get_prime():
    # prime table
    ptb = [True] * MAX_PRIME
    ptb[0] = ptb[1] = False

    for i in range(2, ceil(sqrt(MAX_PRIME)) + 1):
        for j in range(i*2, MAX_PRIME, i):
            ptb[j] = False

    P = [ i for i, v in enumerate(ptb) if v == True]

    return P

def prime_factorization(n, P):
    factor = defaultdict(int)
    for p in P:
        while n % p == 0:
            factor[p] += 1
            n //= p

    if n != 1:
        factor[n] += 1

    return factor

def main():
    P = get_prime()    

    A_fact = list()
    lcm = defaultdict()
    for a in A:
        a_fact = prime_factorization(a, P)
        A_fact.append(a_fact)
        for prime, power in a_fact.items():
            if prime not in lcm:
                lcm[prime] = power
            else:
                if lcm[prime] < power:
                    lcm[prime] = power

    ret = 0
    for a_fact in A_fact:
        b_fact = {key: lcm[key] - a_fact.get(key, 0) for key in lcm.keys()}
        tmp = 1
        for prime, power in b_fact.items():
            tmp *= prime**power
            tmp %= MODE
        ret += tmp
        ret %= MODE

    print(ret)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions 

N = int(input())
A = list(map(int, input().split()))
MODE = 10**9+7

def lcm(a, b):
    return a*b//fractions.gcd(a,b)

_lcm = 1
for a in A:
    _lcm = lcm(a, _lcm)

ret = 0
for a in A:
    ret += (_lcm // a)

print(ret%MODE)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
set_A = set(A)
len_types = len(set_A)
memo = [0] * N
ans = 0

for num in set_A:
    count_num = A.count(num)
    memo[num-1] = count_num

memo.sort()

for i in memo[:N-K]:
    ans += i

# while len_types > K:
#     ans += heapq.heappop(memo)
#     len_types -= 1

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
memo = [0] * N
ans = 0

for a in A:
    memo[a-1] += 1
    
memo.sort()

for i in memo[:N-K]:
    ans += i

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

from math import ceil, log
from operator import __or__

N = int(input())
S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

abc = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))

S2 = [abc[s] for s in S]


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * (2 ** (1 + ceil(log(length, 2))) - 1)
        self.origin = len(self.data) // 2

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, k * 2 + 1, l, (l + r) // 2),
                self._query(start, stop, k * 2 + 2, (l + r) // 2, r),
            )


segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    segs[S2[i]].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        i = int(q2) - 1
        segs[S2[i]].update(i, False)
        letter = abc[q3]
        segs[letter].update(i, True)
        S2[i] = letter
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)



### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    Q = int(input())
    t = [input().split() for _ in range(Q)]

    d = [0] * n + [1 << ord(c) - 97 for c in s]
    for i in range(n - 1, 0, -1):
        d[i] = d[i + i] | d[i - ~i]
    for q, a, b in t:
        i, s = int(a) + n - 1, 0
        if q < "2":
            d[i] = 1 << ord(b) - 97
            while i > 1:
                i //= 2
                d[i] = d[i + i] | d[i - ~i]
        else:
            j = int(b) + n
            while i < j:
                if i & 1:
                    s |= d[i]
                    i += 1
                if j & 1:
                    j -= 1
                    s |= d[j]
                i //= 2
                j //= 2
            print(bin(s).count("1"))


main()
### BUGGY CODE ###

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)


@lru_cache(maxsize=None)
def rec(i, j):
    if i < 0 or j < 0:
        return 0.0
    if i == 0 and j == 0:
        return 1.0
    global p
    return rec(i - 1, j) * (1 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1]


def main():
    N = int(input())
    global p
    p = list(map(float, input().split()))
    ans = 0
    for i in range(N + 1):
        for j in range(N+1):
            ret = rec(N, i)
            if j == N and i > N // 2:
                ans += ret
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    p_mul = 1
    dp[0][0] = 1
    for i in range(1, N + 1):
        p_mul *= (1-p[i-1])
        dp[i][0] = p_mul
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = dp[i - 1][j] * \
                (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1]
    print(sum(dp[N][N//2+1:]))


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

a, b, c = map(int, input().split())
modb = []
for n in range(a, b+1):
  if n % c == 0:
    modb.append(n)
print(len(modb))


### FIXED CODE ###

a, b, c = map(int, input().split())
n = a % c
if n == 0:
  print((b-a)//c+1)
elif c > a:
  print((b-c)//c+1)
else:
  print((b-a+n)//c)
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(input())

    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if j-i == k-j:
                    continue
                if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                    ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())

    ans = s.count("R")*s.count("G")*s.count("B")
    for i in range(n):
        for j in range(i+1, n):
            k = j + j - i
            if k < n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans -= 1
    print(ans)


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

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

for i in range(Q):
  B, C = map(int, input().split())
  A = [C if i == B else i for i in A]
  print(sum(A))

### FIXED CODE ###

# ans

N = int(input())
A = list(map(int, input().split()))
cnt = [0] * 100001
for i in A:
  cnt[i] += 1
Q = int(input())
S = sum(A)

for i in range(Q):
  B, C = map(int, input().split())
  diff = (C - B) * cnt[B]
  S += diff
  print(S)
  cnt[C] += cnt[B]
  cnt[B] = 0
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
#print(h)
DP = [10**9]*N
DP[0] = 0
DP[1] = abs(h[1]-h[0])
for i in range(2,N):
    for j in range(max(i-K,0),i):
        DP[i] = min(DP[i], DP[j] + abs(h[i]-h[j]))
    #print(DP[i])
print(DP[-1])
    


### FIXED CODE ###


def frog2(H,N,K):
    #print(H)
    DP = [10**10]*N
    #DP = [0]*N
    DP[0] = 0
    DP[1] = abs(H[1]-H[0])
    for i in range(2,N):
        for j in range(1,K+1):
            DP[i] = chmin(DP[i],DP[i-j]+abs(H[i]-H[i-j]))
    return DP[-1]

def chmin(a,b):
    if a < b:
        return a
    else:
        return b

if __name__ == '__main__':
    N,K = map(int,input().split())
    H = list(map(int,input().split()))
    ans = frog2(H,N,K)
    print(ans)
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
C = []

H.append(max(H)+1)
for s in range(N):
  i = 0
  while H[s+i] >= H[s+i+1]:
    i += 1
  C.append(i)
print(max(C))

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
C = [0]

for i in range(1, len(H)):
  if H[i-1] < H[i]:
    C.append(i)
C.append(N)
    
D = [C[j+1] - C[j] - 1 for j in range(len(C)-1)]

print(max(D))
### BUGGY CODE ###

from heapq import heappop, heappush
n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = set()
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
    elif any(working):
        dist[x] = min(working)
    else:
        walker.append(x)

for d in dist:
    print(str(d))

### FIXED CODE ###

from heapq import heappush, heappop


n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = set()
heap = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
        heappush(heap, x)
    elif working:
        while not heap[0] in working:
            heappop(heap)
        dist[x] = heap[0]

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

n,k,*a=map(int,open(i:=0).read().split())
a.sort()
p=a.pop
s=b=~k%2or p()
exec(k//2*'if(x:=a[i]*a[i+1])*b>a[-1]*a[-2]*b:s*=x;i+=2\nelse:s*=p()*p()\ns%=10**9+7\n')
print(s)

### FIXED CODE ###

def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if n==k or k%2 and not x:
        c=1
        for i in sorted(x+y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [0]*13
dp[0] = 1

tmp = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * tmp + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * tmp + x
            new[next_x % 13] = dp[x]

    dp = new
    tmp *= 10 % 13

ans = dp[5] % mod
print(ans)


### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [0]*13
dp[0] = 1

mul = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * mul + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * mul + x
            new[next_x % 13] = dp[x]

    dp = new
    mul *= 10
    mul %= 13

ans = dp[5] % mod
print(ans)
### BUGGY CODE ###

k ,s = map(int, input().split())

count = 0
for x in range(k+1):
    for y in range(k +1):
        for z in range(k + 1):
            if x + y + z == s:
                count += 1
                
print(count)

### FIXED CODE ###

k ,s = map(int, input().split())

count = 0
for x in range(min(k+1,s + 1)):
    for y in range(x,min(x+k+1,s +1)):
        if s - y <=k:
                
            count += 1
print(count)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, S: str):
    answer = 0
    for i in range(1000):
        target = str(i).zfill(3)
        index = 0
        for i in range(N):
            if S[i] == target[index]:
                index += 1
            
            if index == 3:
                answer += 1
                break
    
    print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, S: str):
    answer = 0
    for i in range(0,1000):
        i = str(i).zfill(3)
        index = 0
        for ss in S:
            if ss == i[index]:
                index += 1
                if index >= 3:
                    answer += 1
                    break

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, S)

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

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

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
d = deque()
for i in S:
    d.append(i)
flag = True
for _ in range(Q):
    q = [i for i in input().split()]
    if int(q[0]) == 1:
        flag = not flag
    else:
        if (int(q[1]) == 1 and flag) or (int(q[1]) == 2 and not flag):
            d.appendleft(q[2])
        else:
            d.append(q[2])
S = ""
while(len(d)>0):
    if flag:
        S += d.popleft()
    else:
        S += d.pop()
print(S)
### BUGGY CODE ###

import copy
N = 10**15
K = [[1, N]]
for i in range(2, max(int(N**0.5)+1, 2)):
    if N % i == 0:
        K.append([i, N//i])

ans = 3*N
for i in range(len(K)):
    a, b = K[i]
    p = copy.copy(b)
    while(True):
        if b > ans:
            break
        if (2*b-1) % a == 0:
            ans = min(ans, 2*b-1)
        elif (2*b+1) % a == 0:
            ans = min(ans, 2*b)
        if b % 2 == 1:
            if ((b - 1) // 2) % a == 0:
                ans = min(ans, b - 1)
            elif ((b + 1) // 2) % a == 0:
                ans = min(ans, b)
        b += p

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    print(ans)

### FIXED CODE ###

import math
def extgcd(a, b):
    """
    ax + by = gcd(a,b) = d となる (x,y,d) を返す
    """
    if b == 0:
        return (1, 0, a)
    q, r = a // b, a % b
    x, y, d = extgcd(b, r)
    s, t = y, x - q * y
    return s, t, d

def inv_mod(a, N):
    """
    ax = 1 mod N となる x を返す
    """
    return extgcd(a, N)[0]

def CRT(a_1, a_2, m_1, m_2):
    """
    x = a_1 mod m_1, x = a_2 mod m_2 となる x を返す
    """
    y = (a_2 - a_1) * inv_mod(m_1, m_2) % m_2
    return a_1 + m_1 * y

N = int(input())
N *= 2
K = [[1, N]]
for i in range(2, max(int(N**0.5)+1, 2)):
    if N % i == 0:
        K.append([i, N//i])

ans = float("inf")
for i in range(len(K)):
    a, b = K[i]
    if math.gcd(a, b) == 1:
        P = CRT(0, -1, a, b)
        if P != 0:
            ans = min(P, ans)
        Q = CRT(0, -1, b, a)
        if Q != 0:
            ans = min(Q, ans)

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

print(sum(range(int(input()))))

### FIXED CODE ###

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

s=[int(x) for x in input()]
L=[]
sum=0
for i in range(len(s)):
    t=s[i]*(10**(len(s)-i))
    sum += t
    L.append(sum%2019)
L.sort()

ans=0
count=1
for i in range(len(L)-1):
    if L[i]==L[i+1]:
        count += 1
    else:
        if L[i]==0:
            count += 1
        if count>1:
            ans += count*(count-1)//2
        count=1
if count>1:
    ans += count*(count-1)//2

print(ans)


### FIXED CODE ###

from collections import deque
s=input()[::-1]
l=[0]*2019
ten=1
sm=0
cnt=0
l[0]=1
for i in range(len(s)):
    sm += int(s[i])*ten
    sm %= 2019
    cnt += l[sm]
    l[sm] += 1
    ten = ten *10 %2019
print(cnt)
### BUGGY CODE ###

n,a,b = [int(i) for i in input().split()]
mod = 10**9+7

def mpow(a,n):
  if n == 0:
    return 1
  x = mpow(a,n//2)
  ans = x*x%mod
  if n%2==1:
    ans *= a
  return ans

def comb(n,a,b):
  if a < b:
    s, l = a, b
  else:
    s, l = b, a
  r1s = 1
  for i in range(s):
    r1s = r1s*(n-i)%mod
  r1l = r1s
  for i in range(s,l):
    r1l = r1l*(n-i)%mod
  r2s = 1
  for i in range(1,s+1):
    r2s = r2s*mpow(i,mod-2)%mod
  r2l = r2s
  for i in range(s+1,l+1):
    r2l = r2l*mpow(i,mod-2)%mod
  nCs = r1s*r2s
  nCl = r1l*r2l
  if a < b:
    nCa, nCb = nCs, nCl
  else:
    nCa, nCb = nCl, nCs
  return nCa, nCb
nCa,nCb = comb(n,a,b)
print((mpow(2,n)-1-nCa-nCb)%mod)
# print(nCa)

### FIXED CODE ###

import math
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*pow(i,mod-2,mod)%mod
  return ans

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

import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
if (n-1==k):
    print(m**m)
    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod
#print(ans)
p = pow(m-1,n-k-2,mod)
#com(n-1,i,mod)
c = com(n-1,k+1,mod)
#print(c)
for i in range(k,0,-1):
    p *= (m-1)
    p %= mod
    c *= (i+1)
    c *= pow(n-i-1,mod-2,mod)
    c %= mod
    ans += m * p * c
    ans %= mod
    #print(m-1,i,mod)
    #print(ans)
print(ans)

### FIXED CODE ###

import copy
n,m,k = map(int, input().split())
if m==1:
    if (n-1==k):
        print(1)
    else:
        print(0)
    exit()

mod = 998244353
if (n-1==k):
    print(pow(m,n,mod))
    exit()
#dp[i][j]:i個まで、j組
def com(n,r,m):
    #a = math.factorial(n)%m
    a = 1
    for i in range(1,n+1):
        a *= i
        a %= m
    A = pow(a,m-2,m)
    
    
    b= copy.deepcopy(A)   
    for i in range(n,r,-1):
        b = (b*i)%m
    
    c = copy.deepcopy(A)
    for i in range(n,n-r,-1):
        c = (c*i)%m
       
    return (a*b*c)%m

ans = m*pow(m-1,n-1,mod)
ans %= mod
#print(ans)
p = pow(m-1,n-k-2,mod)
#com(n-1,i,mod)
c = com(n-1,k+1,mod)
#print(c)
for i in range(k,0,-1):
    p *= (m-1)
    p %= mod
    c *= (i+1)
    c *= pow(n-i-1,mod-2,mod)
    c %= mod
    ans += m * p * c
    ans %= mod
    #print(m-1,i,mod)
    #print(ans)
print(ans)
### BUGGY CODE ###

N, T = map(int, input().split())
num_list = input().split()
num_list = [int(x) for x in num_list]

dif = 0
count = 0

for index, i in enumerate(num_list):
    for j in num_list[index:]:
   #     print(j)
        if j > i and (j - i) >= dif:
            dif = j - i

for index, i in enumerate(num_list):
    for j in num_list[index:]:
        if j - i == dif:
            count += 1

print(count)

### FIXED CODE ###

N, T = map(int, input().split())
num_list = input().split()
num_list = [int(x) for x in num_list]

count = 0
profit = 0
min_val = num_list[0]

for num in num_list:
    if num < min_val:
        min_val = num
    elif num - min_val == profit:
        count += 1
    elif num - min_val > profit:
        count = 1
        profit = num - min_val

print(count)