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

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)
    


### FIXED CODE ###

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

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            if l >= K:
                temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    if l >= K:
        temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)
### BUGGY CODE ###

n, m, k = map(int, input().split())
mod =998244353

if n == 1:
    print(m)
    exit()

X = [[0]*(k+2) for _ in range(k+2)]
for i in range(k+2):
    if i == 0:
        continue
    X[i][i-1] = 1
    X[i][i] = m-1

def mul(a, b):
    c = [[0]*len(b[0]) for i in range(len(a))]
    for i in range(len(a)):
        for k in range(len(b)):
            for j in range(len(b[0])):
                c[i][j] = (c[i][j] + a[i][k]*b[k][j])%mod

    return c

#A**n
def pow(a, n):
    b = [[0]*len(a) for i in range(len(a))]
    for i in range(len(a)):
        b[i][i] = 1
    while n > 0:
        if n & 1 == 1:
            b = mul(a, b)
        a = mul(a, a)
        n = n>>1
    return b

#print(X)
Y =  pow(X, n-1)
#Z0 = [0]*(k+2)
#Z[1] = m
ans = 0
#print(Y)
for i in range(k+2):
    ans += Y[i][1]*m
print(ans%mod)


### FIXED CODE ###

n, m, k = map(int, input().split())
mod =998244353

def cmb1(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

ans = 0
for x in range(k+1):
    temp = cmb1(n-1, x, mod)
    temp *= m*power(m-1, n-1-x, mod)
    ans += temp
print(ans%mod)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(list(map(int,input().split())))
b=list(zip(*a))
c=sorted(b[1])
d=[0]*n
for i in c:
  j=b[0][b[1].index(i)]-1
  d[j]+=1
  a[b[1].index(i)][1]=d[j]
for i in range(m):
  print('{0:06}{1:06} '.format(a[i][0],a[i][1]))

### FIXED CODE ###

from heapq import heappush, heappop
n,m=map(int,input().split())
data=[]
pn=[0 for _ in range(n)]
for i in range(m):
  p,y=map(int,input().split())
  heappush(data,(y,p,i))
data2=[]
while data:
  y,p,i=heappop(data)
  pn[p-1]+=1
  cid=str(p).zfill(6)+str(pn[p-1]).zfill(6)
  data2.append((i,cid))
for i,cid in sorted(data2):
  print(cid)
### BUGGY CODE ###

n = int(input())
temp_list = []
for _ in range(n):
    a = input()
    if a in temp_list:
        temp_list.remove(a)
    else:
        temp_list.append(a)
print(len(temp_list))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
d = defaultdict(int)
for _ in range(n):
    a = input()
    d[a] += 1
ans = sum([v % 2 for v in d.values()])
print(ans)
### BUGGY CODE ###

def resolve():
    N, C, K = map(int, input().split())
    T = [int(input()) for _ in range(N)]
    T.sort()
    
    count_bus = 0
    
    i = 0
    while i < len(T):
        # print('T[{}]: {}'.format(i, T[i]))
        t = T[i]
        for j in range(1, C):
            if i+j >= len(T):
                i += j
                count_bus += 1
                break
    
            if T[i+j] <= t + K:
                pass
                if j == C-1:
                    i += j + 1
                    count_bus += 1
                    break
    
            else:
                count_bus += 1
                i += j
                break
    
    print(count_bus)


if __name__ == '__main__':
    resolve()

### FIXED CODE ###

N, C, K = map(int, input().split())
T = [int(input()) for _ in range(N)]
T.sort()

# print(T)

bus = 1
org = T[0]
_count = 0

for t in T:

    if t - org <= K and _count < C:
        _count += 1
        # print('1- t:{}, org:{}, _count:{}, bus:{}'.format(t, org, _count, bus))
    else:
        bus += 1
        org = t
        _count = 1
        # print('2- t:{}, org:{}, _count:{}, bus:{}'.format(t, org, _count, bus))

print(bus)
### BUGGY CODE ###

from collections import Counter


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

for k in range(N):
    c_a = count_A.copy()
    c_a[A[k]] -= 1
    ans = 0
    for v in c_a.values():
        ans += v*(v-1)//2
    print(ans)

### FIXED CODE ###

from collections import Counter


N = int(input())
A = list(map(int, input().split()))
count_A = Counter(A)
sum_A = sum([i*(i-1)//2 for i in count_A.values()])

for k in range(N):
    n = count_A[A[k]]
    ans = sum_A - n + 1
    print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = sorted(LI(), reverse=True)
cnt = 0
hq = [(-A[i] - A[0], i, 0) for i in range(n)]
heapify(hq)
for i in range(m):
    x, l, r = heappop(hq)
    cnt -= x
    if r != n - 1:
        heappush(hq, (-A[l] - A[r + 1], l, r + 1))

print(cnt)







### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = sorted(LI(), reverse=True)
max_num = 10 ** 5 * 2 + 1
D = [0] * max_num
acc = [0] + A
for i in range(1, n):
    acc[i + 1] += acc[i]

for i in A:
    D[i] += 1

for i in range(max_num - 1, 0, -1):
    D[i - 1] += D[i]

ok = 1
ng = max(A) * 2 + 1
while ng > ok + 1:
    mid = (ng + ok) // 2
    ret = 0
    happiness = 0
    for i in range(n):
        d = D[max(mid - A[i], 0)]
        ret += d
    if ret >= m:
        ok = mid
    else:
        ng = mid


ret2 = 0
ans = 0
for i in range(n):
    d2 = D[max(ng - A[i], 0)]
    ret2 += d2
    ans = ans + d2 * A[i] + acc[d2]

ans += (m - ret2) * ok
print(ans)
### BUGGY CODE ###

mod=10**9+7
def num2bi(x, k):
  #10進数xを2進数k桁(string)で出力
  out=format(x, '0'+str(k)+'b')
  return out

N=int(input())
A=list(map(int, input().split()))
ma=max(A)
keta=1
while ma>=2**keta:
  keta+=1
  
onekazu=[0 for i in range(keta)]
k=str(keta)
for i in range(N):
  temp=format(A[i], '0'+str(k)+'b')
  for j in range(keta):
    if temp[j]=='1':
      onekazu[j]+=1
    
out=0
out=sum([(onekazu[i]*(N-onekazu[i])%mod)*(2**(keta-1-i))%mod for i in range(keta)])
out%=mod  
print(out)

### FIXED CODE ###

mod=10**9+7
def num2bi(x, k):
  #10進数xを2進数k桁(string)で出力
  out=format(x, '0'+str(k)+'b')
  return out

N=int(input())
A=list(map(int, input().split()))
ma=max(A)
keta=1
while ma>=2**keta:
  keta+=1
  
onekazu=[0 for i in range(keta)]
k=str(keta)
for i in range(N):
  temp=format(A[i], '0'+str(k)+'b')
  onekazu=[onekazu[j]+1 if temp[j]=='1' else onekazu[j] for j in range(keta)]
    
out=0
out=sum([(onekazu[i]*(N-onekazu[i])%mod)*(2**(keta-1-i))%mod for i in range(keta)])
out%=mod  
print(out)
### BUGGY CODE ###



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

ans = 0

for i, p in enumerate(P):
    if any([True for p2 in P[0:i] if p2 < p]):
        pass
    else:
        ans += 1

print(ans)


### FIXED CODE ###

from itertools import accumulate

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

ans = 0

"""
for i, p in enumerate(P):
    # if np.any(P[0:i] < p): あまり以下と変わらなかった
    # if any([True for p2 in P[0:i] if p2 < p]): # 2回のループが☓ O(n^2)なので
        pass
    else:
        ans += 1
"""

P_min = list(accumulate(P, min))

for p, p_min in zip(P, P_min):
    if p == p_min:
        ans += 1

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

n = int(input())
a = list(map(int, input().split()))
len_a = len(a)
range_a = range(len_a)
result = []

for i in range_a:
    for j in range_a:
        if i < j:
            result.append(a[i] * a[j])

print(sum(result) % (10 ** 9 + 7))


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
sum_a = sum(a)
count = 0
for i, v in enumerate(a):
    sum_a -= v
    count += v * sum_a

print(count % (10 ** 9 + 7))
### BUGGY CODE ###

from collections import defaultdict
def solve():
    N = int(input())
    progression = list(map(int, input().split()))
    cuml = [0]*(N+1)
    for i in range(len(progression)):
        cuml[i+1] = cuml[i] + progression[i]
    cuml_dic = defaultdict(list)
    for i, num in enumerate(cuml):
        cuml_dic[num].append(i)
    ans = 0
    for i in range(1, N+1):
        if cuml[i] == 0:
            ans += 1
        for index in cuml_dic[cuml[i]]:
            if index > i:
                ans += 1
    print(ans)



solve()

### FIXED CODE ###

from collections import defaultdict
def solve():
    N = int(input())
    progression = list(map(int, input().split()))
    cuml = [0]*(N+1)
    for i in range(len(progression)):
        cuml[i+1] = cuml[i] + progression[i]
    cuml_dic = defaultdict(list)
    for i, num in enumerate(cuml):
        cuml_dic[num].append(i)
    ans = 0
    for key, value in cuml_dic.items():
        n = len(value)-1
        ans += int((n+1)*n/2)

    print(ans)

solve()
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
# l = list()
# r = list()
s_list = list()
for _ in range(q):
    l_i, r_i = map(int, input().split())
    # l.append(l_i)
    # r.append(r_i)
    s_list.append(s[l_i-1:r_i])

for i in range(q):
    print(s_list[i].count('AC'))


### FIXED CODE ###

def main():
    # n, q = map(int, input().split())
    # s = input()
    # # l = list()
    # # r = list()
    # s_list = list()
    # # s_tuple = tuple()
    # for _ in range(q):
    #     l_i, r_i = map(int, input().split())
    #     # l.append(l_i)
    #     # r.append(r_i)
    #     s_list.append(s[l_i - 1:r_i])
    #     # s_tuple = s_tuple + tuple(s[l_i - 1:r_i])
    # 
    # s_tuple = tuple(s_list)
    # 
    # for i in s_tuple:
    #     print(i.count('AC'))
    N, Q = map(int, input().split())
    S = input()
    cnt = [0] * (N + 1)
    for i in range(N):
        cnt[i + 1] = cnt[i] + (1 if S[i:i+2] == 'AC' else 0)
    for i in range(Q):
        l, r = map(int, input().split())
        print(cnt[r - 1] - cnt[l - 1])


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

n = int(input())
count = 0

for i in range(1, n):
  count += i

print(count)


### FIXED CODE ###

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

n = int(input())
sum = 0
for i in range(n):
    sum += i

print(sum)


### FIXED CODE ###

n = int(input())
if n % 2 == 0:
    sum = int(n/2)
    sum = sum *(n-1)

else:
    sum = int((n-1)/2)
    sum = sum * n

print(int(sum))
### BUGGY CODE ###

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

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

ans = 0

for i in range(k+1):
    for j in range(k+1):
        k2 = s - j - i

        if k2 > k or k2 < 0:
            continue

        if s == i + j + k2:
            ans += 1

print(ans)


### FIXED CODE ###

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

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

ans = 0

for i in range(k+1):
    for j in range(k+1):
        k2 = s - j - i

        if k2 > k or k2 < 0:
            continue

        if s == i + j + k2:
            ans += 1

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

N,M,R=map(int,input().split())
r=list(map(int,input().split()))

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))



Dis=[10**8]*(N+1)

for i in range(N+1):
    Dis[i]=[10**8]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]


#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(1,N+1):#町jとの最短距離は、
            Dis[i][j]=min(Dis[i][j],Dis[i][k]+Dis[j][k])
    
        
import itertools
    
PERM=list(itertools.permutations(r,R))

ANS=10**8
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
    ANS=min(ANS,DIST)


print(ANS)


### FIXED CODE ###

#import numpy as np
import itertools
import time

N,M,R=map(int,input().split())
r=list(map(int,input().split()))

ROAD=[None]*M

for i in range(M):
    ROAD[i]=list(map(int,input().split()))


#Dis=np.full((N+1,N+1),float("inf"))

Dis=[None]*(N+1)
for i in range(1,N+1):
    Dis[i]=[100000000]*(N+1)

for i in range(M):
    Dis[ROAD[i][0]][ROAD[i][1]]=ROAD[i][2]
    Dis[ROAD[i][1]][ROAD[i][0]]=ROAD[i][2]



#ワーシャル–フロイド法を使って最短距離Disを求める

for k in range(1,N+1):#k個までの町を使ってのDisが知れているときに
    for i in range(1,N+1):#町iと
        for j in range(i,N+1):#町jとの最短距離は、
            length=Dis[i][k]+Dis[j][k]
            if Dis[i][j]>length:
                Dis[i][j]=length
                Dis[j][i]=length


  
PERM=list(itertools.permutations(r))



ANS=float("inf")
for i in range(len(PERM)):
    DIST=0
    for k in range(1,R):
        DIST+=Dis[PERM[i][k]][PERM[i][k-1]]
        if DIST>ANS:
            break
    if ANS>DIST:
        ANS=DIST

print(int(ANS))
### BUGGY CODE ###

# coding: utf-8
n = int(input())
A = list(map(int,input().split()))
#素朴な解法(むり)
ans = 0
for i in range(n):
    flg=False
    for j in range(n):
        if i!=j and A[i]%A[j]==0:
            flg=True
    if not flg:
        ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
n = int(input())
A = list(map(int,input().split()))
a_ = max(A)
A_ = list(set(A))
dp = [True] * (a_+1)
C = [0] * (a_+1)
for a in A:
    C[a]+=1
A_.sort()
ans = 0

for a in A_:
    tmp = a
    if dp[tmp]:
        tmp += a
        while tmp <= a_:
            dp[tmp] = False
            tmp += a
#print(dp)
for a in A_:
    if dp[a]:
        if C[a]==1:
            ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, size, type, num):
    q = deque(maxlen=size)
    q.append(start)
    used = {start}
    groups[type].append(used)
    groups_inv[type][start] = num
    while q:
        node = q.popleft()
        for to in graphs[i][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[type][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, n, i, count)
            count += 1

ret = [1] * n
ret_inv = [[-1] * n for _ in range(n)]
for i in range(n):
    if groups_inv[0][i] == -1 or groups_inv[1][i] == -1:
        continue
    if ret_inv[groups_inv[0][i]][groups_inv[1][i]] == -1:
        size = len(groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]])
        ret_inv[groups_inv[0][i]][groups_inv[1][i]] = size
    ret[i] = size

print(*ret)


### FIXED CODE ###

from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, case, num):
    q = deque()
    q.append(start)
    used = {start}
    groups[case].append(used)
    groups_inv[case][start] = num
    while q:
        node = q.popleft()
        for to in graphs[case][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[case][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, i, count)
            count += 1

ret = [-1] * n
for i in range(n):
    if groups_inv[0][i] == -1 or groups_inv[1][i] == -1:
        ret[i] = 1
    elif ret[i] == -1:
        cities = groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]]
        for city in cities:
            ret[city] = len(cities)
print(*ret)
### BUGGY CODE ###

import sys
import math
import bisect
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
Bl=[[] for i in range(10**5+5)]

for i in range(N):
    A,B=nm()
    Bl[A].append(B)

now=Bl[0]
ans=0
for i in range(1,M+2):
    if(now!=[]):
        max_val=max(now)
        ans+=max_val
        now.remove(max_val)
    now=now+Bl[i]

print(ans)

### FIXED CODE ###

import sys
import math
import bisect
import heapq
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
Bl=[[] for i in range(10**5+5)]

for i in range(N):
    A,B=nm()
    Bl[A].append(-B)

now=[]
if(Bl[0]!=[]):
    for i in range(len(Bl[0])):
        heapq.heappush(now,Bl[0][i])

ans=0
for i in range(1,M+2):
    if(now!=[]):
        max_val=heapq.heappop(now)
        ans+=max_val
    if(Bl[i]!=[]):
        for j in range(len(Bl[i])):
            heapq.heappush(now,Bl[i][j])

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

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=(3**(n-1))%mod
for i in range(1,n):
  if l[i]=='0':
    dp[i]=dp[i-1]
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans+=(dp[i-1]*(3**(n-i-1)))%mod
print((ans+dp[n-1])%mod)


### FIXED CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=[0]*n
ans[0]=1
for i in range(1,n):
  if l[i]=='0':
    dp[i]=(dp[i-1])%mod
    ans[i]=(ans[i-1]*3)%mod
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans[i]=(ans[i-1]*3+dp[i-1])%mod
print((ans[n-1]+dp[n-1])%mod)
### BUGGY CODE ###

S=input()
Word=['eraser','erase','dreamer','dream']

while True:
    if len(S)<4:
        break
    else:
        for i in Word:
          S = S.replace(i,"")
           
if len(S)==0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

S=input()
Word=['eraser','erase','dreamer','dream']

while True:
    S_len=len(S)
    if S_len<5:
        break
    else:
        for i in Word:
            S = S.replace(i,"")
        if len(S)==S_len: #一つも文字が消えなかった時break
            break
           
if len(S)==0:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n = int(input())
num = input()
 
password_list = []
initial_list = []
initial_list2 = []
initial_list3 = []
 
for i in range(len(num)-2):
    if num[i] in initial_list:
        continue
    else:
        initial_list.append(num[i])
        for j in range(i+1,len(num)-1):
            initial_list2 = []
            if num[j] in initial_list2:
                continue
            else:
                initial_list2.append(num[j])
                for k in range(j+1,len(num)):
                    initial_list3 = []
                    if num[k] in initial_list3:
                        continue
                    else:
                        initial_list3.append(num[k])
                        target = num[i] + num[j] + num[k]
                        if target not in password_list:
                            password_list.append(target)
print(len(password_list))

### FIXED CODE ###

n = int(input())
num = input()
 
password_list = []
initial_list = []
initial_list2 = []
initial_list3 = []
 
for i in range(len(num)-2):
    initial_list2 = []
    if num[i] in initial_list:
        continue
    elif len(initial_list) == 10:
        break
    else:
        initial_list.append(num[i])
        for j in range(i+1,len(num)-1):
            initial_list3 = []
            if num[j] in initial_list2:
                continue
            elif len(initial_list2) == 10:
                break
            else:
                initial_list2.append(num[j])
                for k in range(j+1,len(num)):
                    if num[k] in initial_list3:
                        continue
                    elif len(initial_list3) == 10:
                        break
                    else:
                        initial_list3.append(num[k])
                        target = num[i] + num[j] + num[k]
                        if target not in password_list:
                            password_list.append(target)
                            
print(len(password_list))
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,n+1):
    if i in a:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
step = [0] * (n+1)
step[0] = 1
if 1 not in a:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,n+1):
    if i in a:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ans = 0
for i in range(N):
  j = N-2
  temp = 0
  while j > i:
    if temp > 0:
      k = temp
    else:
      k = N - 1
    while k > j:
      if L[i]-L[j]-L[k] < 0:
        ans += k-j
        temp = k
        break
      k -=1
    j -= 1
  
print(ans)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ck = [0]*(N-2)
ans = 0
for i in range(N-2):
  j = i + 1
  k = N - 1
  while j < k:
    if L[i]-L[j]-L[k] < 0:
      ans += k-j
      j += 1 
    else:
      k -=1
  
print(ans)