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

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

import bisect

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B, C = [0]*M, [0]*M
for i in range(M):
    B[i], C[i] = map(int, input().split())

A.sort()    # 昇順ソートO(NlogN)

for i in range(M):
    idx = bisect.bisect_left(A, C[i])
    if idx > 0:
        for j in range(min(idx,B[i])):
            A[j] = C[i]
        A.sort()

print(sum(A))

### FIXED CODE ###

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

import bisect

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
BC = [0]*M
for i in range(M):
    BC[i] = [int(n) for n in  input().split()]

A.sort()    # 昇順ソートO(NlogN)
BC.sort(key=(lambda x: x[1]), reverse=True)   # Ciの値で降順ソート

st = 0 # 編集開始位置
for i in range(M):  # O(MlogN)
    b, c = BC[i]
    idx = bisect.bisect_left(A, c, st)  # A全体でのidxを返す
    edit = idx - st # 編集個数
    edit = min(b, edit)
    for j in range(edit):
        A[st+j] = c
    st += edit

print(sum(A))
### BUGGY CODE ###

# ABC061_C
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

lst = []

for i in range(N):
    for j in range(AB[i][1]):
        lst += [AB[i][0]]

lst = sorted(lst)
print(lst[K-1])


### FIXED CODE ###

# ABC061_C
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(AB)

for i in range(N):
    K -= AB[i][1]
    if K <= 0:
        print(AB[i][0])
        break
### BUGGY CODE ###

n,c,k = map(int, input().split())
t = [int(input()) for i in range(n)]
t.sort()
ans = 1
while len(t) > 1:
    d = t[0]
    m = min(len(t),c)-1
    if t[m]-k <= d:
        t = t[m+1:]
    else:
        i = 0
        while 1:
            i += 1
            if t[i]-k > d:
                break
        t = t[i:]
    if len(t):
        ans += 1
print(ans)

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,c,k = LI()
    t = IR(n)
    t.sort()
    i = 0
    ans = 0
    while i < n:
        i = min(i+c,bisect.bisect_right(t, t[i]+k))
        ans += 1
    print(ans)
    return
#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()
### BUGGY CODE ###

a = input().split()

L = int(a[0])
R = int(a[1])

mm = 2018

for i in range(L , R + 1):
  for j in range(L , R + 1):
    if i < j:
      n = (i * j) % 2019
      if n < mm:
        mm = n
print (mm)

### FIXED CODE ###

import sys
a = input().split()

L = int(a[0])
R = int(a[1])
if R - L == 2019:
  print(0)
  sys.exit()

mm = 2018

for i in range(L , R + 1):
  for j in range(L , R + 1):
    if i < j:
      n = (i * j) % 2019
      if n == 0:
        print(0)
        sys.exit()
      elif n < mm:
        mm = n
print (mm)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = ["?"]*N

    l, x, r = 0, N//2, N-1
    while True:
        ls = A[l]
        if ls == "?":
            print(l, flush=True)
            ls = input().strip()
            if ls == "Vacant":
                return
            A[l] = ls

        xs = A[x]
        if xs == "?":
            print(x, flush=True)
            xs = input().strip()
            if xs == "Vacant":
                return
            A[x] = xs

        rs = A[r]
        if rs == "?":
            print(r, flush=True)
            rs = input().strip()
            if rs == "Vacant":
                return
            A[r] = rs

        if ls != xs:
            if (x-l) % 2:
                l, x, r = x, (x+r)//2, r
            else:
                l, x, r = l, (l+x)//2, x
        elif rs != xs:
            if (r-x) % 2:
                l, x, r = l, (l+x)//2, x
            else:
                l, x, r = x, (x+r)//2, r
        else:
            l, x, r = x, (x+r)//2, r


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def q(i):
    print(i, flush=True)
    s = input().strip()
    if s == "Vacant":
        exit()
    return s


def f(l, r, lc, rc):
    m = (l+r)//2
    mc = q(m)

    if ((m-l) % 2 and lc == mc) or ((m-l) % 2 == 0 and lc != mc):
        f(l, m, lc, mc)
    elif ((r-m) % 2 and mc == rc) or ((r-m) % 2 == 0 and mc != rc):
        f(m, r, mc, rc)


def main():
    N = int(input())
    lc = q(0)
    rc = q(N-1)
    f(0, N-1, lc, rc)


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

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 4 + 7

N = int(input())

A = [0] * N
for i in range(N):
    A[i] = int(input())

d = []
for a in A:
    l = -1
    r = len(d)
    while r - l > 1:
        m = l + (r - l) // 2
        if d[m] >= a:
            r = m
        else:
            l = m
    if r == 0:
        d = [a] + d
    else:
        d[r - 1] = a
print(len(d))

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 4 + 7

N = int(input())

A = [0] * N
for i in range(N):
    A[i] = int(input())

from collections import deque
d = deque([])
for a in A:
    l = -1
    r = len(d)
    while r - l > 1:
        m = l + (r - l) // 2
        if d[m] >= a:
            r = m
        else:
            l = m
    if r == 0:
        d.appendleft(a)
    else:
        d[r - 1] = a
print(len(d))
### BUGGY CODE ###

n , k = map(int,input().split())
a = list(map(int,input().split()))
b = []
for i in range(n):
    for j in range(i,n):
        b.append(sum(a[i:j+1]))
ans = 0
for i in reversed(range(41)):
    cou = 0
    now = ans + 2**i
    for j in b:
        if j & now >= now:
            cou += 1
    if cou >= k:
        ans += 2**i
print(ans)

### FIXED CODE ###

n , k = map(int,input().split())
a = list(map(int,input().split()))
b = []
for i in range(n):
    for j in range(i,n):
        b.append(sum(a[i:j+1]))
ans = 0
for i in reversed(range(41)):
    cou = 0
    now = ans + 2**i
    for j in b:
        if j & now >= now:
            cou += 1
    if cou >= k:
        ans += 2**i
print(ans)
### BUGGY CODE ###

from collections import deque
from copy import deepcopy

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "#":
            continue
        ss = deepcopy(s)
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            ss[y][x] = "#"
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if ss[ny][nx] == ".":
                        q.append((cost,ny,nx))
        m = max(m,max_cost)
print(m)

### FIXED CODE ###

from collections import deque
from copy import deepcopy

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "#":
            continue
        ss = deepcopy(s)
        ss[sy][sx] = "#"
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if ss[ny][nx] == ".":
                        q.append((cost,ny,nx))
                        ss[ny][nx] = "#"
        m = max(m,max_cost)
print(m)
### BUGGY CODE ###

from collections import defaultdict
import math
sieve=[1]*10001
i=2
while i*i<=10001:
    if sieve[i]:
        for j in range(i+i,10001,i):
            sieve[j]=0
        
    i+=1    
lol=[]
for i in range(2,10001):
    if sieve[i]:
        lol.append(i)
mod=10**9+7
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)    
x=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in a:
    k=0

    while lol[k]*lol[k]<=i:
        c=0
        #print("AScasc",i)
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                c+=1
            d[j]=max(c,d[j])    
        k+=1    
    if i>=2:
        c=1
        d[i]=max(c,d[i])
        
y=0
s=d.keys()
#print(s,d)
for i in a:
    d0=d.copy()
    k=0
    while lol[k]*lol[k]<=i:
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                d0[j]-=1
        k+=1
    if i>=2:
        d0[i]-=1
    z=1
    for j in d0.keys():
        z*=pow(j,d0[j],mod)
    y+=z%mod    
print(y%mod)        

### FIXED CODE ###

from collections import defaultdict
import math
sieve=[1]*10001
i=2
while i*i<=10001:
    if sieve[i]:
        for j in range(i+i,10001,i):
            sieve[j]=0
        
    i+=1    
lol=[]
for i in range(2,10001):
    if sieve[i]:
        lol.append(i)
mod=10**9+7
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)    
x=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in a:
    k=0

    while lol[k]*lol[k]<=i:
        c=0
        #print("AScasc",i)
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                c+=1
            d[j]=max(c,d[j])    
        k+=1    
    if i>=2:
        c=1
        d[i]=max(c,d[i])
        
y=0
s=d.keys()
#print(s,d)
z=1
for i in s:
    z*=pow(i,d[i])
for i in a:
    y+=((z%mod)*pow(i,mod-2,mod))%mod
print(y%mod)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l+=[min(l[i-j]+abs(b-a[i-j])for j in range(1,min(k,i)+1))]
print(l[-1])

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l.append(min(l[j]+abs(b-a[j])for j in range(i-min(k,i),i)))
print(l[-1])
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    point = [1] * (K)
    point[0] = A[0]

    for i in range(1, K):
        point[i] = point[i - 1] * A[i]

    ans = point[K - 1]
    for i in range(N - K):
        tmp = ans * A[K + i] / A[i]
        if ans < tmp:
            print('Yes')
        else:
            print('No')
        ans = tmp


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    ans = ['No'] * (N - K)
    for i in range(N - K):
        tmp = A[K + i] / A[i]
        if 1 < tmp:
            ans[i] = 'Yes'
    print("\n".join(ans))


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

import itertools
def warshall_floyd(g):
    for k in range(len(g)):
        for i in range(len(g)):
            for j in range(len(g)):
                g[i][j] = min(g[i][j], g[i][k]+g[k][j])
    return g

n,m,r = map(int,input().split())
lst = list(map(int,input().split()))
graph = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0
d = warshall_floyd(graph)

res = float('inf')
for l in itertools.permutations(lst):
    cnt = 0
    for i in range(1, len(l)):
        cnt += d[l[i-1]-1][l[i]-1]
    res = min(res, cnt)
print(res)

### FIXED CODE ###

import itertools
def warshall_floyd(g):
    for k in range(len(g)):
        for i in range(len(g)):
            for j in range(len(g)):
                g[i][j] = min(g[i][j], g[i][k]+g[k][j])
    return g

n,m,r = map(int,input().split())
lst = list(map(int,input().split()))
graph = [[float('inf')]*n for _ in range(n)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
for i in range(n):
    graph[i][i] = 0
d = warshall_floyd(graph)

res = float('inf')
for l in itertools.permutations(lst):
    cnt = 0
    for i in range(1, len(l)):
        cnt += d[l[i-1]-1][l[i]-1]
    res = min(res, cnt)
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in range(1<<N):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print(dp[-1][i])


### FIXED CODE ###

import sys
input = sys.stdin.readline

INF = float('inf')

N = int(input().strip())
data = [list(map(int, input().split())) for _ in range(N)]
cost_b = []
cost_D = []
for b in range(1<<N):
  towns = []
  cost = INF
  for i in range(N):
    if (b>>i)&1:
      towns.append(data[i])
  for i in range(len(towns)):
    X = towns[i][0]
    cost = min(cost,sum(abs(towns[j][0]-X)*towns[j][2] for j in range(len(towns))))
  for i in range(len(towns)):
    Y = towns[i][1]
    cost = min(cost,sum(abs(towns[j][1]-Y)*towns[j][2] for j in range(len(towns))))
  if len(towns) == 0:
    cost = 0
  cost_b.append(cost)
  cost_D.append(sum(min(abs(towns[j][0]),abs(towns[j][1]))*towns[j][2] for j in range(len(towns))))

dp = [[INF]*(N+1) for i in range(1<<N)]

for i in range(1<<N):
  dp[i][0] = cost_D[i]
count = 0
for k in range(1,N+1):
  for i in reversed(range(1<<N)):
    x = i
    while x>=0:
      x &= i
      new = dp[i-x][k-1]+cost_b[x]
      if dp[i][k] > new:
        dp[i][k] = new
      if new == 0:
        break
      x -= 1
for i in range(N+1):
  print(dp[-1][i])
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n]),sorted(a[n:])[::-1]
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
                if l<0:
                    ng=mid
                    break
        else:ok=mid
    print(ok)
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()
### BUGGY CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)

### FIXED CODE ###

s = input()
L = len(s)
MOD = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(L + 1)]
dp[0][0] = 1

for i in range(1, L + 1):
    if s[i - 1] == "?":
        for j in range(10):
            for k in range(13):
                dp[i][(k * 10 + j) % 13] += dp[i - 1][k] % MOD
    else:
        for k in range(13):
            dp[i][(k * 10 + int(s[i - 1])) % 13] += dp[i - 1][k] % MOD

print(dp[-1][5] % MOD)
### BUGGY CODE ###

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = set()
    dp.add(0)
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K - a - 1, -1, -1):
            if j in dp:
                dp.add(j + a)
    rst = any(k in dp for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, -1, -1):
                dp[min(K, j + a)] |= dp[j]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()
### BUGGY CODE ###

from collections import defaultdict, deque

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

G = defaultdict(lambda: defaultdict(int))

for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x

# solve
values_sum[1] = values[1]

queue = deque([1])
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if G[p][q] == 1 and values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)

print(*values_sum[1:])


### FIXED CODE ###

from collections import defaultdict

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

G = defaultdict(list)

for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x

# solve
values_sum[1] = values[1]

queue = [1]
while len(queue) > 0:
    p = queue.pop()
    for q in G[p]:
        if values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)

print(*values_sum[1:])
### BUGGY CODE ###

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

if n % 2 == 0 and n//2 == x:
    print(3 * x)
    exit()

if x > n // 2:
    x = n - x

xx = x
yy = n - x

ans = n
i = 0
f = False

while True:
    if yy >= xx:
        ans += 2 * xx
        yy -= xx

        if yy == 0:
            ans -= xx
            f = True
            break

        if f:
            break

    if xx > yy:
        ans += yy * 2
        xx -= yy

        if xx == 0:
            ans -= yy
            f = True
            break

        if f:
            break

print(ans)


### FIXED CODE ###

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

if n % 2 == 0 and n//2 == x:
    print(3 * x)
    exit()

if x > n // 2:
    x = n - x

xx = x
yy = n - x


ans = n
i = 0

while True:
    
    if yy >= xx:
        ans += 2 * (yy // xx) * xx
        yy %= xx

        if yy == 0:
            ans -= xx
            break

        if yy < xx:
            tmp = xx
            xx = yy
            yy = tmp

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

#!/usr/bin/env python3

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

count = 0
for i in range(N):
    l = P[:i+1]
    # print(l)
    if P[i] <= min(l):
        count += 1

print(count)


### FIXED CODE ###

#!/usr/bin/env python3

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

count = 0
min_prev = P[0] + 1
for i in range(N):
    if P[i] < min_prev:
        min_prev = P[i]
        count += 1

print(count)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for _ in range(Q)]
for i in range(1,N+1):
  a = A.count(i)
  if  K - (Q - a) > 0:
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [0]*Q
score = []
for i in range(Q):
  A[i] = int(input())
for _ in range(N):  
  score.append(K-Q)
for i in range(Q):
  a =  A[i]
  score[a-1] += 1

for j in range(N):
  if score[j] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
A = list(int(input()) for _ in range(M))

mod = 10**9+7

# dp[i] : i番目の階段までの場合の数
dp = [0]*(N+1) 
dp[0] = 1
dp[1] = 1 if 1 not in A else 0 

for i in range(2,N+1):
    if i not in A:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N])


### FIXED CODE ###

# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
A = list(int(input()) for _ in range(M))

mod = 10**9+7

# 床が壊れてる階段を高速に判別できるように
B = [True]*(N+1)
for a in A:
    B[a] = False

# dp[i] : i番目の階段までの場合の数
dp = [0]*(N+1) 
dp[0] = 1
dp[1] = 1 if 1 not in A else 0 

for i in range(2,N+1):
    if B[i]:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N])
### BUGGY CODE ###

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

mod = 998244353

dp = [[0] * n for _ in range(3000 + 1)]

# init
dp[a[0]][0] = 1

for i in range(1, s + 1):
    for j in range(1, n):
        if i == a[j]:
            dp[i][j] = dp[i][j-1] + j + 1
        elif i - a[j] > 0:
            dp[i][j] = dp[i][j-1] + dp[i - a[j]][j - 1]
        else:
            dp[i][j] = dp[i][j-1]

ans = 0
for j in range(n):
    ans += dp[s][j]

print(ans % mod)


### FIXED CODE ###

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

mod = 998244353

dp = [[0] * n for _ in range(3000 + 1)]

# init
dp[a[0]][0] = 1

for i in range(1, s + 1):
    for j in range(1, n):
        if i == a[j]:
            dp[i][j] = (dp[i][j-1] + j + 1) % mod
        elif i - a[j] > 0:
            dp[i][j] = (dp[i][j-1] + dp[i - a[j]][j - 1]) % mod
        else:
            dp[i][j] = dp[i][j-1] % mod



ans = 0
for j in range(n):
    ans += dp[s][j]

print(ans % mod)