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

from statistics import mode
from math import factorial

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


# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

X = factorial(N+1) % MOD
O = factorial(outside) % MOD

for k in range(1, len(A)+1):
    if k > outside + 1:
        Y = pow((factorial(k)) * factorial(N+1-k) % MOD, MOD-2, MOD)
        print((X * Y) % MOD)
    else:
        Y = pow((factorial(k)) * factorial(N+1-k) % MOD, MOD - 2, MOD)
        Y2 = pow((factorial(k-1)) * factorial(outside - k + 1) % MOD, MOD - 2, MOD)
        print(((X * Y) % MOD - (O * Y2) % MOD))


### FIXED CODE ###

from statistics import mode

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

# 2回表れている値とそのインデックスを取得
C = mode(A)
C_indexes = [i for i, x in enumerate(A) if x == C]

# 二つのCの外側にそれぞれ何個ずつあるか
outside = C_indexes[0] + len(A) - C_indexes[1] - 1

# 階乗・逆元の値を保存
factorial = [1]
inverse = [1]
for i in range(1, N+2):
    factorial.append(factorial[-1]*i % MOD)
    inverse.append((pow(factorial[i], MOD-2, MOD)))

# combination計算
def nCr(n, r):
    if n<r or n==0 or r==0:
        return 0
    return factorial[n] * inverse[r] * inverse[n-r] % MOD


print(N)
for i in range(2, N+2):
    print(int(nCr(N+1, i) - nCr(outside, i-1)) % MOD)
### BUGGY CODE ###

h, w = map(int, input().split())
field = [input() for _ in range(h)]

hor = [[0 for _ in range(w)] for _ in range(h)]
ver = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    count = 0
    for j in range(w):
        if field[i][j] == '#':
            for k in range(j-count, j):
                hor[i][k] = count
            count = 0
            hor[i][j] = 0
        else:
            count += 1
    for k in range(w-count, w):
        hor[i][k] = count

for j in range(w):
    count = 0
    for i in range(h):
        if field[i][j] == '#':
            for k in range(i-count, i):
                ver[k][j] = count
            count = 0
            ver[i][j] = 0
        else:
            count += 1
    for k in range(h-count, h):
        ver[k][j] = count

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hor[i][j] + ver[i][j] - 1)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
field = [input() for _ in range(h)]

hor = [[0 for _ in range(w)] for _ in range(h)]
ver = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    count = 0
    for j in range(w):
        if field[i][j] == '#':
            for k in range(j-count, j):
                hor[i][k] = count
            count = 0
            hor[i][j] = 0
        else:
            count += 1
    for k in range(w-count, w):
        hor[i][k] = count

for j in range(w):
    count = 0
    for i in range(h):
        if field[i][j] == '#':
            for k in range(i-count, i):
                ver[k][j] = count
            count = 0
            ver[i][j] = 0
        else:
            count += 1
    for k in range(h-count, h):
        ver[k][j] = count

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hor[i][j] + ver[i][j] - 1)
print(ans)
### BUGGY CODE ###

n = int(input())
P = list(map(int, input().split(' ')))

count = 0
for i in range(n):
    if i == 0:
        count += 1
    elif min(P[i], min(P[:i])) == P[i]:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
P = list(map(int, input().split(' ')))

count = 0
minimum = 2 * 10 ** 5 + 1
for p in P:
    if p < minimum:
        count += 1
        minimum = p
print(count)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = [1]

c = 1
for i in range(k):
    c = a[c]
    if c not in b:
        b.append(c)
        if i == k-1: print(c); sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

# print(b,idx,sn,bn)
kk = (k-sn) % bn
print(b[idx+kk])

### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

n,k = [int(x) for x in stdin.readline().rstrip().split()]
a = [0] + [int(x) for x in stdin.readline().rstrip().split()]

m = 0
b = [1]
visited = [-1 for i in range(n+1)]

c = 1
visited[1] = 1
for i in range(n):
    c = a[c]
    if visited[c] != 1:
        b.append(c)
        visited[c] = 1
        if i == k-1:
            print(c)
            sys.exit()
    else:
        break

idx = b.index(c)
bn = len(b[idx:])
sn = len(b[:idx])

# print(b,idx,sn,bn)
kk = (k-sn) % bn
print(b[idx+kk])
### BUGGY CODE ###

from numpy.linalg import solve

N = int(input())
right = list(int(x) * 2 for x in input().split())
 
left = []

for i in range(N):
    num = []
    for j in range(N):
        if j == i or j == (i + 1):
            num.append(1)
        else:
            num.append(0)
        if i == N - 1:
            num[0] = 1        
    left.append(num)

answer = ""
for a in solve(left, right):
    answer += str(int(a))
    answer += " "

print(answer)

### FIXED CODE ###

import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

N = int(input())
a_ = list(int(x) for x in input().split())
X_ = [0 for _ in range(N)]

X_sum = sum(a_)
logging.info("sum = " + str(X_sum))

X_[0] = X_sum - 2 * sum(a_[1::2])
logging.info("X_1 = " + str(X_[0]))

for i in range(1, N):
    X_[i] = 2 * a_[i - 1] - X_[i - 1]

answer = ""
for i in X_:
    answer += str(i)
    answer += " "

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

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n,m = map(int,input().split())

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1)
#print(len_s2)
count = 0
for ix, vs1 in enumerate(len_s1):
    for jx in range(count,len(len_s2)):
        #print(vs1, len_s2[jx])
        if vs1 < len_s2[jx]:
            break
        if vs1 == len_s2[jx]:
            count = jx
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
            break
print(len_moji)

### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n,m = map(int,input().split())

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1)
#print(len_s2)
count = 0
for ix, vs1 in enumerate(len_s1):
    for jx in range(count,len(len_s2)):
        #print(vs1, len_s2[jx])
        if vs1 < len_s2[jx]:
            count = jx-1
            break
        if vs1 == len_s2[jx]:
            count = jx
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
            break
print(len_moji)
### BUGGY CODE ###

NK = input().split()
N, K = int(NK[0]), int(NK[1])
lis_p = list(map(lambda x: int(x), input().split()))
#lis_exp = list(map(lambda x: (int(x)+1)/2, input().split()))
dp=0
best_i = 0
for i in range(N):
    if sum(lis_p[i:i+K]) >= dp:
        best_i = i
    dp = max(sum(lis_p[i:i+K]), dp)
res = sum(list(map(lambda x: (int(x)+1)/2, lis_p[best_i:best_i+K])))
print(res)

### FIXED CODE ###

N, K = map(int, input().split())
lis_p = map(int, input().split())
def calc_exp(x):
    return (int(x) + 1)/2
lis_exp = list(map(calc_exp, lis_p))
dp= sum(lis_exp[0:K])
cumKsum = sum(lis_exp[0:K])
for i in range(1, N-K+1):
    cumKsum = cumKsum - lis_exp[i-1] + lis_exp[i+K-1]
    dp = max(cumKsum, dp)
print(dp)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
temp=0
for i in range(n):
    temp=a.pop(0)
    print(max(a))
    a.append(temp)

### FIXED CODE ###

n=int(input())
A=[int(input()) for _ in range(n)]
maxm=sorted(A)
ans=[]
for i in range(n):
    if A[i]==maxm[-1]:
        ans.append(maxm[-2])
    else:
        ans.append(maxm[-1])
for a in ans:
    print(a)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
MAX = max(A)
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**(0.5)+1)):
        if not is_prime[i]:
            continue
        for j in range(i*2,n+1,i):
            is_prime[j] = False
    return is_prime
prime = primes(MAX)
pri = [i for i in range(2,MAX+1) if prime[i]]
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = defaultdict(int)
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] += cnt
    if temp!=1:
        arr[temp] = 1
    if len(arr) == 0:
        arr[n] = 1
    return arr
c = factorization(A[0])
for i in range(1,N):
    nex = factorization(A[i])
    for j in pri:
        aa = max(c[j],nex[j])
        c[j] = aa
ans = 0
for i in range(N):
    a = A[i]
    p = factorization(a)
    plus = 1
    for j in pri:
        plus *= pow(j,c[j]-p[j],MOD)
    ans += plus
    ans %= MOD
print(ans)




    

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
L = A[0]
for i in range(1,N):
    g = math.gcd(L,A[i])
    L = L*A[i]//g
ans = 0
L %= MOD
for i in range(N):
    ans += (L*pow(A[i],MOD-2,MOD))
    ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
a = 0
pw = [0] * n
pw[0] = 1
for i in range(1, n):
    pw[i] = pw[i - 1] * 2
for i in range(n):
    if s[i] == '1':
        a += int(pw[n - i - 1])
v = bin(a).count('1')
for i in range(n):
    add = int(pw[n - i - 1])
    if s[i] == '1':
        add *= -1
    copy = a + add
    x = v
    if s[i] == '1':
        x -= 1
    else:
        x += 1
    cnt = 1
    if copy == 0:
        cnt = 0
    while x > 0 and copy % x != 0:
        copy %= x
        x = bin(copy).count('1')
        cnt += 1
    print(cnt)
    
        


### FIXED CODE ###

n = int(input())
s = input()
pw, pw1, pw2 = [0] * n, [0] * n, [0] * n
pw[0], pw1[0], pw2[0] = 1, 1, 1
v, mod1, mod2 = 0, 0, 0
for i in range(n):
    if s[i] == '1':
        v += 1
for i in range(1, n):
    pw1[i] = int(pw1[i - 1] * 2) % (v + 1)
    if v >= 2:
        pw2[i] = int(pw2[i - 1] * 2) % (v - 1)
for i in range(n):
    if s[i] == '1':
        mod1 = (mod1 + pw1[n - i - 1]) % (v + 1)
        if v >= 2:
            mod2 = (mod2 + pw2[n - i - 1]) % (v - 1)    
for i in range(n):
    copy, x, cnt = 0, v, 1
    
    if s[i] == '0':
        x += 1
        copy = (mod1 + pw1[n - i - 1]) % x
    else:
        x -= 1
        if x >= 1:
            copy = (mod2 - pw2[n - i - 1]) % x
        else:
            copy = -1
    if copy == -1:
        print(0)
    else:
        x = bin(copy).count('1')
        while copy > 0:
            copy %= x
            x = bin(copy).count('1')
            cnt += 1
        print(cnt)
### BUGGY CODE ###

x = int(input())
num = 101000
arr = list(range(2,num))
arr = set(arr)
primes = {2}

prime = min(arr)
while prime < num-500:
    primes.add(prime)
    nonprime = {prime * i for i in range(1,num//prime + 2)}
    arr = arr.difference(nonprime)
    prime = min(arr)

sol = {i for i in primes if i >= x}

print(min(sol))

### FIXED CODE ###

x = int(input())
num = 100200
arr = list(range(2,num))
arr = set(arr)
primes = {2}
floor = int(num**0.5)+2

prime = min(arr)
while prime < floor:
    prime = min(arr)
    primes.add(prime)
    nonprime = {prime * i for i in range(1,num//prime + 2)}
    arr = arr.difference(nonprime)

primes = primes.union(arr)

sol = {i for i in primes if i >= x}

print(min(sol))
### BUGGY CODE ###

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

while(1):
  m=abs(n-k)

  if m>n:
    print(n)
    break
  else:
    n=m

### FIXED CODE ###

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

x=n%k

y=abs(x-k)

if x<y:
  print(x)
else:
  print(y)
### BUGGY CODE ###

N, M = map(int, input().split(" "))

P = []
S = []

clear = 0

q = {}
c = []

for i in range(M):
    sss = input().split(" ")
    p = int(sss[0])
    s = sss[1]
    P.append(p)
    S.append(s)

    if p not in c:
        if s == "AC":
            clear += 1
            c.append(p)

        if s == "WA":
            q[p] = q.get(p, 0) + 1

warng = 0
for k, v in q.items():
    if k in c:
        warng += v

print("{} {}".format(clear, warng))

### FIXED CODE ###

N, M = map(int, input().split(" "))

P = []
S = []

clear = 0

q = {}
c = set()

for i in range(M):
    sss = input().split(" ")
    p = int(sss[0])
    s = sss[1]
    P.append(p)
    S.append(s)

    if p not in c:
        if s == "AC":
            clear += 1
            c.add(p)

        if s == "WA":
            q[p] = q.get(p, 0) + 1

warng = sum([
    q[k]
    for k in c
    if k in q
])

print("{} {}".format(clear, warng))
### BUGGY CODE ###

A, B = [int(_) for _ in input().split()]

R = 0
tmp = B
while tmp > 1:
    tmp = tmp // 2
    R += 1
ans = [0] * (R + 1)

memo = [[A, B]]
for i in range(R, -1, -1):
    v = 2 ** i
    for j in range(len(memo)):
        a, b = memo[j]
        if b >= v:
            ans[i] += b - v + 1 - max(a - v, 0)
            if b - v > 0:
                memo.append([max(a - v, 0), b - v])
            if a < v:
                memo[j] = [a, v - 1]
            else:
                memo[j] = [0, 0]

ans = ''.join([str(_ % 2) for _ in reversed(ans)])
print(int(ans, 2))


### FIXED CODE ###

def solve(n):
    """ f(0, n) """

    n += 1
    res = 0
    for i in range(0, 40):
        t2 = (1 << i)
        # i桁の周期が完全に何回でてくるか
        x = n // (t2 * 2)
        cnt = x * t2
        # あまり分(0 * t2 のあと 1 * t2 の順で出現)
        cnt += max(0, n % (t2 * 2) - t2)

        res += t2 * (cnt % 2)
    return res


a, b = [int(_) for _ in input().split()]
# print(solve(b))
# print(solve(a-1))
print(solve(b) ^ solve(a-1))
### BUGGY CODE ###

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

A.append(0)
for i in range(N):
    b, s = 0, 0
    for j, a in enumerate(A):
        if i != j:
            s += abs(b - a)
            b = a
    print(s)


### FIXED CODE ###

from collections import deque
N = int(input())
A = [0] + list(map(int, input().split())) + [0]

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

visited = []
for i in range(1, N + 1):
    a = abs(A[i - 1] - A[i + 1])
    b = abs(A[i] - A[i - 1]) + abs(A[i] - A[i + 1])
    visited.append(total + (a - b))

for v in visited:
    print(v)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
t=np.int32(sorted(map(int,input().split())))
dp=np.ones((k+t.max()),dtype='int32')*-1
dp[:t[0]]=0
for i in range(k):
    dp[t+i]=np.maximum((dp[i]+1)%2,dp[t+i])
print(['Second','First'][dp[k]%2])

### FIXED CODE ###

n,k=map(int,input().split())
t=sorted(map(int,input().split()))
dp=[-float('inf')]*(k+1)
dp[:t[0]]=[0]*t[0]
for i in range(k):
    for j in range(n):
        if i+t[j]<k+1:
            dp[i+t[j]]=max(dp[i+t[j]],(dp[i]+1)%2)
print(['Second','First'][dp[-1]%2])
### BUGGY CODE ###

V = int(input())
A = []
for _ in range(V):
    A.append(list(map(int, input().split())))

ret = 0
for i in range(V):
    for j in range(i+1, V):
        f = True
        for k in range(V):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                f = False
        if f:
            ret += A[i][j]

print(ret)


### FIXED CODE ###

V = int(input())
A = [list(map(int, input().split())) for _ in range(V)]

ret = 0
for i in range(V):
    for j in range(i+1, V):
        f = True
        for k in range(V):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                f = False
        if f:
            ret += A[i][j]

print(ret)
### BUGGY CODE ###

import copy
A, B = [], []
N, M = (int(x) for x in input().split())
for i in range(N):
    a, b = (int(x) for x in input().split())
    A.append(a), B.append(b)

#sort main_list with sub_list
def merge(main_list, sub_list):
    mid = len(main_list)
    if mid > 1:
        left = merge(main_list[:(mid//2)], sub_list[:(mid//2)])
        right = merge(main_list[(mid//2):], sub_list[(mid//2):])
        main_list, sub_list = [], []
        while len(left[0]) != 0 and len(right[0]) != 0:
            if left[0][0] < right[0][0]:
                main_list.append(left[0].pop(0))
                sub_list.append(left[1].pop(0))
            else:
                main_list.append(right[0].pop(0))
                sub_list.append(right[1].pop(0))
        if len(left[0]) != 0:
            main_list.extend(left[0])
            sub_list.extend(left[1])
        elif len(right[0]) != 0:
            main_list.extend(right[0])
            sub_list.extend(right[1])
    return main_list, sub_list

num_of_drink, total_fee = 0, 0
A, B = copy.copy(merge(A, B)[0]), copy.copy(merge(A, B)[1])

temp_M = M
list_of_num = []
for i in range(N):
    if temp_M <= B[i]:
        list_of_num.append(temp_M)
        break
    else:
        list_of_num.append(B[i])
        temp_M += -B[i]
index = 0
for x in list_of_num:
    total_fee += A[index] * x
    index += 1
print(total_fee)

### FIXED CODE ###

List = []
N, M = (int(x) for x in input().split())
for i in range(N):
    a, b = (int(x) for x in input().split())
    List.append([a, b])

num_of_drink, total_fee = 0, 0
List = sorted(List, key=lambda x:x[0])

temp_M = M
list_of_num = []
for i in range(N):
    if temp_M <= List[i][1]:
        list_of_num.append(temp_M)
        break
    else:
        list_of_num.append(List[i][1])
        temp_M += -List[i][1]
index = 0
for x in list_of_num:
    total_fee += List[index][0] * x
    index += 1
print(total_fee)
### BUGGY CODE ###

x = int(input())
s = {0}
ans = 0
i = 1
while x not in s:
	t = set()
	for u in s:
		t |= {u + i, u, u - i}
	s = t
	i += 1

print(i - 1)

### FIXED CODE ###

x = int(input())
i = 1
while i * (i + 1) / 2 < x:
	i += 1
print(i)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*N
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        for x in range(g,h+1):
            A2[x-1]+=1
    A=A2[:]
    A2 = [0]*N

print(*A)

### FIXED CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*(N+1)
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        A2[g-1]+=1
        A2[h]-=1
    A[0]=A2[0]
    for j in range(1, N):
        A[j]=A[j-1]+A2[j]
    A2 = [0]*(N+1)
    c = 0
    for p in range(N):
        c+=A[p]
    if c >= N*N:
        break

print(*A)
### BUGGY CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
S = nl()
T = nl()

import numpy as np
dp = np.zeros(M+1, dtype=np.int64)
for i, s in enumerate(S):
    dp2 = np.zeros(M+1, dtype=np.int64)
    dp2[1:] = dp[1:] - dp[:M]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print(int(dp[M]+1) % 1000000007)


### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
S = nl()
T = nl()

dp = [0] * (M+1)
for i, s in enumerate(S):
    dp2 = dp[:]
    for j, t in enumerate(T):
        dp2[j+1] += dp2[j] - dp[j]
        if s == t:
            dp2[j+1] += dp[j] + 1
    dp = dp2

print((dp[M]+1) % 1000000007)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    sushis = [[] for _ in range(N)]
    for i in range(N):
        t, d = map(int, input().split())
        sushis[t-1].append(d)
    for i in range(N):
        sushis[i].sort(reverse=True)
        cumsum = 0
        for j in range(len(sushis[i])):
            cumsum += sushis[i][j]
            sushis[i][j] = cumsum
    dp = [[None] * (K+1) for _ in range(2)]
    dp[1][0] = (0, 0)
    dp[0][0] = (0, 0)
    for i in range(N):
        dp[i % 2] = [x for x in dp[(i-1) % 2]]
        for j in range(len(sushis[i])):
            for k in range(K-j):
                if dp[(i-1) % 2][k] is None:
                    continue
                pt, pd = dp[(i-1) % 2][k]
                if dp[i % 2][k+j+1] is None or pd + sushis[i][j] + 2 * pt + 1 >= dp[i % 2][k+j+1][1]:
                    dp[i % 2][k+j+1] = (pt+1, pd + sushis[i][j] + 2 * pt + 1)
    print(dp[(N-1) % 2][K][1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, K = map(int, input().split())
    sushis = [None] * N
    for i in range(N):
        t, d = map(int, input().split())
        sushis[i] = (t, d)
    sushis.sort(key=lambda a: (-a[1], a[0]))
    tmp = 0
    types = set()
    stack = deque()
    ans = 0
    for i in range(len(sushis)):
        t, d = sushis[i]
        if i < K:
            if t in types:
                stack.append(d)
            types.add(t)
            tmp += d
        else:
            if t not in types and len(stack):
                types.add(t)
                tmp += d
                tmp -= stack.pop()
        ans = max(ans, tmp + len(types)**2)
    print(ans)


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

n,k = (int(x) for x in input().split())
list = list(map(int,input().split()))
if n>k:
	for i in range(k):
		list.remove(max(list))
	print(sum(list))
else:
	print(0)

### FIXED CODE ###

n,k = (int(x) for x in input().split())
list = list(map(int,input().split()))
if n>k:
	list2=sorted(list)
	print(sum(list2[:n-k]))
else:
	print(0)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]

d = {}

for i in range(N):
    if a[i] not in d:
        d[a[i]] = 1
    else:
        d[a[i]] += 1

for i in range(N):
    d[a[i]] -= 1

    su = 0
    for j in d.values():
      su += int(j * (j - 1) / 2)
    print(su)

    d[a[i]] += 1

### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

total = 0
for v in d.values():
    if v != 1 and v != 0:
        total += int(v * (v - 1) / 2)

for i in range(N):
    tmp = d[A[i]] - 1
    print(total - tmp)