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

tuple=input()
list=tuple.split()
list=[int(i) for i in list]
N=list[0]
Y=list[1]
for i in range(int(Y/10000)+1):
    for j in range(int((Y-10000*i)/5000)+1):
        for k in range(int((Y-10000*i-5000*j)/1000)+1):
            if 10000*i+5000*j+1000*k==Y and i+j+k==N:
                print(i,j,k)
                exit()
print("-1 -1 -1")


### FIXED CODE ###

tuple=input()
list=tuple.split()
list=[int(i) for i in list]
N=list[0]
Y=list[1]
for i in range(int(Y/10000)+1):
    for j in range(int((Y-10000*i)/5000)+1):
            if 10000*i+5000*j+1000*(N-i-j)==Y :
                print(i,j,N-i-j)
                exit()
print("-1 -1 -1")
### BUGGY CODE ###

N = int(input())

nums = list(map(int,input().split(" ")))
s = 1
for num in nums:
    s = s * num
if s > 10**18:
    print(-1)
else:
    print(s)
    


### FIXED CODE ###

N = int(input())

nums = list(map(int,input().split(" ")))
s = 1
limit = 10**18
flag = False
for num in nums:
    s = s * num
    if s > limit:
        flag = True
        break

if flag:
    if 0 not in nums:
        print(-1)
    else:
        print(0)
else:
    print(s)
### BUGGY CODE ###

from collections import defaultdict

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

dp = [[-1] * (1<<n) for i in range(n)]
pre = [1<<i for i in range(n)]
DP = [defaultdict(lambda : float("inf")) for i in range(n)]

for i in range(n):
    DP[i][1<<i] = 0

for i in range(n-1):
    nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
    for j in range(n):
        last = a[j] if (i-j)%2 == 0 else b[j]
        for state, cost in DP[j].items():
            for to in range(n):
                if state>>to&1:
                    continue
                nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                if last > nlast:
                    continue
                nstate = state + pre[to]
                ncost = cost
                for k in range(to+1, n):
                    if state&pre[k]:
                        ncost += 1
                nxt[to][nstate] = min(nxt[to][nstate], ncost)
    DP = nxt
mask = (1<<n)-1
ans = float("inf")
for i in range(n):
    ans = min(ans, DP[i][mask])
if ans == float("inf"):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

from collections import defaultdict

def main():

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

    if all(a[0] == a[i] for i in range(n)):
        print(0)
        exit()

    pre = [1<<i for i in range(n)]
    bitcnt = [0]*(1<<n)
    bitcnt[1] = 1
    for i in range(1<<(n-1)):
        bitcnt[2*i] = bitcnt[i]
        bitcnt[2*i+1] = bitcnt[i]+1

    DP = [defaultdict(lambda : float("inf")) for i in range(n)]

    for i in range(n):
        DP[i][1<<i] = 0
    s = defaultdict(lambda : float("inf"))
    for i in range(n-1):
        nxt = [defaultdict(lambda : float("inf")) for i in range(n)]
        for j in range(n):
            last = a[j] if (i-j)%2 == 0 else b[j]
            for state, cost in DP[j].items():
                for to in range(n):
                    if state>>to&1:
                        continue
                    nlast = a[to] if (i+1-to)%2 == 0 else b[to]
                    if last > nlast:
                        continue
                    nstate = state|pre[to]
                    ncost = cost
                    ncost += bitcnt[state>>to]
                    if s[(nstate, nlast)] <= ncost:
                        continue
                    s[(nstate, nlast)] = ncost
                    if nxt[to][nstate] > ncost:
                        nxt[to][nstate] = ncost
        DP = nxt
    mask = (1<<n)-1
    ans = float("inf")
    for i in range(n):
        ans = min(ans, DP[i][mask])
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

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

t = 0
SENTINEL = 1e+9


def sort(a, b):
    global t
    a.append(SENTINEL)
    b.append(SENTINEL)
    i, j = 0, 0
    while i < len(a)-1 or j < len(b)-1:
        t += 1
        if a[i] < b[j]:
            yield a[i]
            i += 1
        else:
            yield b[j]
            j += 1


def merge(a, left, mid, right):
    left_list, right_list = a[left:mid], a[mid:right]
    for index, value in zip(range(left, right), sort(left_list, right_list)):
        a[index] = value


def merge_sort(a, left, right):
    global t
    if right-left == 1:
        return
    elif right-left == 2:
        t += 2
        a[left], a[right-1] = min(a[left], a[right-1]), max(a[left], a[right-1])
    else:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)


def main():
    global t
    input()
    a = [int(i) for i in input().split()]
    merge_sort(a, 0, len(a))
    print(*a)
    print(t)


if __name__ == '__main__':
    main()



### FIXED CODE ###

SENTINEL = 1e+9
t = 0


def Merge(A, left, mid, right):
    global t
    n1 = mid - left
    n2 = right - mid
    L, R = A[left:left+n1], A[mid:mid+n2]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(left, right):
        t += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def Merge_Sort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        Merge_Sort(A, left, mid)
        Merge_Sort(A, mid, right)
        Merge(A, left, mid, right)


def main():
    global t
    input()
    A = [int(i) for i in input().split()]
    Merge_Sort(A, 0, len(A))
    print(*A)
    print(t)


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

from math import gcd
from operator import mul
from functools import reduce
N = int(input())
*A, = map(int, input().split())

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

if reduce(lcm, A) == reduce(mul, A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print("setwise coprime")
else:
    print('not coprime')

### FIXED CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i


def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p != 1 and p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True


if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

from collections import deque

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

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

cnt = [0 for _ in range(N)]
for _ in range(Q):
  p, x = map(int, input().split())
  p -= 1
  cnt[p] += x

queue = deque()
queue.append((0, -1))
while queue:
  q = queue.popleft()
  if q[0] != 0:
    cnt[q[0]] += cnt[q[1]]
  for i in to[q[0]]:
    if i != q[1]:
      queue.append((i, q[0]))

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

### FIXED CODE ###

from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

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

N=int(input())
A = [int(x) for x in input().split()]
S=[]
for i in range(N):
    for j in range(i+1,N):
        s=A[i]*A[j]
        S.append(s)
print(sum(S)%(10**9+7))
        


### FIXED CODE ###

N=int(input())
A = [int(x) for x in input().split()]
s=sum(A)
x=0
for i in range(N):
    s=s-A[i]
    x+=s*A[i]    
print(x%(10**9+7))
### BUGGY CODE ###

l,r=map(int,input().split())

ans=10000
for i in range(l,r):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%2019)
    if ans==0:
      break
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
ans = 2018
if r - l >= 2019:
    for i in range(l, l + 2019 + 1):
        for n in range(l, i):
            ans = min(ans, (i * n) % 2019)
else:
    for i in range(l, r + 1):
        for n in range(l, i):
            ans = min(ans, (i * n) % 2019)
print(ans)
### BUGGY CODE ###

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

while N > abs(N-K):
    N = abs(N-K)

print(N)

### FIXED CODE ###

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

j = N//K

if N-j*K > -(N-(j+1)*K):
    print(-(N-(j+1)*K))
else:
    print(N-j*K)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
for i in set(A):
  if A.count(i) % 2 != 0:
    ans += 1

print(ans)

### FIXED CODE ###

import collections
N = int(input())
A = [int(input()) for _ in range(N)]
count = collections.Counter(A)

l = []
for i in list(count):
  if count[i] % 2 != 0:
    l.append(count[i])

print(len(l))
### BUGGY CODE ###

N, K = map(int, input().split())
lists = list(map(int, input().split()))
if K == 0:
    print(sum(lists))
    exit()

if K <= len(lists):
    for i in range(K):
        max_lists = lists.remove(max(lists))
else:
    print(0)
    exit()

# print(lists)

print(sum(lists))

### FIXED CODE ###

N, K = map(int, input().split())
lists = list(map(int, input().split()))
if K == 0:
    print(sum(lists))
    exit()

if K <= len(lists):
    # for i in range(K):
    #     max_lists = lists.remove(max(lists))
    lists = sorted(lists)[:N - K]
    print(sum(lists))
    exit()
else:
    print(0)
    exit()

# print(lists)
### BUGGY CODE ###

# 32:35
n = int(input())

heights = list(map(int, input().split()))

values = dict()

for invI, h in enumerate(heights):
    c1 = invI - h
    if (c1) in values:
        values[c1].append((invI, h))
    else:
        values[c1] = [(invI, h)]
    c2 = -invI - h
    if (c2) in values:
        values[c2].append((-invI, h))
    else:
        values[c2] = [(-invI, h)]

count = dict()
for j, h in enumerate(heights):
    if (j + h) in values:
        for i, ai in values[j + h]:
            if i > 0 and i > j and not (j, i) in count:
                count[(j, i)] = True
    if (h - j) in values:
        for invI, ai in values[h - j]:
            i = -invI
            if invI < 0 and j > i and not (i, j) in count:
                count[(i, j)] = True

print(len(count))

### FIXED CODE ###

# 32:35
n = int(input())

heights = list(map(int, input().split()))

values = dict()

for ii, h in enumerate(heights):
    c1 = ii - h
    if (c1) in values:
        values[c1].append((ii, h))
    else:
        values[c1] = [(ii, h)]

count = 0
for j, h in enumerate(heights):
    if (j + h) in values:
        count += len(values[j + h])
        # for i, ai in values[j + h]:
        #     if i > 0 and i > j and not (j, i) in count:
        #         count[(j, i)] = True


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

import sys
sys.setrecursionlimit(100000)
I=lambda:map(int,input().split())
n,m=I()
g=[[]for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a]+=[b]
  g[b]+=[a]

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      return [j]+dfs(j)
      break
  else:
    return []
z=dfs(1)[::-1]+[1]+dfs(1)
print(len(z))
print(*z)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
I=lambda:map(int,input().split())
n,m=I()
g=[set() for _ in range(n+1)]
v=[1 for _ in range(n+1)]
v[1]=0

for _ in range(m):
  a,b=I()
  g[a].add(b)
  g[b].add(a)

def dfs(x):
  for j in g[x]:
    if v[j]:
      v[j]=0
      l=dfs(j)
      l.append(j)
      return l
      break
  else:
    return []
z=dfs(1)+[1]+dfs(1)[::-1]
print(len(z))
print(*z)
### BUGGY CODE ###

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

ans = 0
MOD = 10**9+7

for i in range(n-1):
    for j in range(i+1,n):
        ans += (a[i]^a[j])
    ans %= MOD

print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(input().split(), dtype=int)

ans = 0
MOD = 10**9+7

k = max(a)
j = 0
while k:
    bits = (a>>j)&1
    one = np.count_nonzero(bits)
    ans += (one%MOD)*((n-one)%MOD)*pow(2,j,MOD)
    ans %= MOD
    j += 1
    k >>= 1

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

import sys
input = sys.stdin.buffer.readline


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
while True:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
    if flag:
        break
    day += 1
F = False
for a in A:
    if len(a) != 0:
        F = True
        break
if F:
    print(-1)
else:
    print(day)

### FIXED CODE ###

import sys
# input = sys.stdin.buffer.readline


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [[int(i) for i in input().split()]for _ in range(q)]
count,ans,f = 0,0,0
for j in lr:
  ans = 0
  f = 0
  for i in s[j[0]-1:j[1]]:
    
    if i =='A':
      f = 1
    elif i =='C' and f==1:
      ans+=1
      f =0
    else:
      f = 0
  print(ans)


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = [[int(i) for i in input().split()]for _ in range(q)]
dp = [0]*n
f,c = 0,0
for i,j in enumerate(s):
  if f==1 and j=='C':
    c+=1
    f =0
  elif j=='A':
    f = 1
  else:
    f = 0
  dp[i]=c
for i in lr:
  print(dp[i[1]-1]-dp[i[0]-1])
### BUGGY CODE ###

#---------------for input--------------------
numberN=int(input())
arrayS=list(map(int,input().split()))

numberQ=int(input())
arrayT=list(map(int,input().split()))
#---------------for input----------------------

def linearSearch(arrayS,arrayT,numberQ):
    machedNumber=0
    index=0
    while index<numberQ:
        if arrayT[index] in arrayS:
            machedNumber+=1
        index+=1
    print(machedNumber) 

#----------------for main------------------------
linearSearch(arrayS,arrayT,numberQ)
#----------------for main------------------------


### FIXED CODE ###

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

count = 0
for elT in t:
    minI = 0
    maxI = len(s)-1
    while minI <= maxI:
        middle = (minI+maxI)//2
        if s[middle] == elT:
            count+=1
            break
        elif s[middle] < elT:
            minI = middle+1
        else:
            maxI = middle-1
print(count)
### BUGGY CODE ###

from collections import defaultdict as dd
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
N, Q = map(int, input().split())
e = dd(list)
for i in range(1, N):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = deque([0] * (N + 1))
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
def dfs(n):
  global visited
  global res
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      dfs(o)
dfs(1)
res.popleft()
print(" ".join(map(str, res)))



### FIXED CODE ###

from collections import defaultdict as dd
from collections import deque as dq
N, Q = map(int, input().split())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
  
res = [0] * (N + 1)
for _ in range(Q):
  p, x = map(int, input().split())
  res[p] += x
visited = [0] * (N + 1)
Q = dq([])
Q.append(1)
visited[1] = 1
while len(Q) != 0:
  n = Q.pop()
  visited[n] = 1
  for o in e[n]:
    if visited[o] == 0:
      res[o] += res[n]
      Q.append(o)
#def dfs(n):
#  global visited
#  global res
#  visited[n] = 1
#  for o in e[n]:
#    if visited[o] == 0:
#      res[o] += res[n]
#      dfs(o)
#dfs(1)
sen = ""
for i in range(1, N + 1):
  sen += str(res[i])
  if i != N:
    sen += " "
print(sen)
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
S = [1]

for i in range(0,N):
    tmp = S[-1] * A[i]
    S.append(tmp)

# print(S)

B = []
for i in range(K,N+1):
    B.append(S[i]//S[i-K])

for i in range(1,len(B)):
    if(B[i]>B[i-1]):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(K,N):
    if(A[i]>A[i-K]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

a = input()
n = int(input())
tmp = 0 
for i in range(n):
    q = input().split()
    if len(q) == 1:
        tmp += 1
    elif len(q) == 3:
        if q[1] == '1':
            if tmp % 2 == 0:
                a = q[2] + a
            else:
                a = a + q[2]
        elif q[1] == '2':
            if tmp % 2 == 0:
                a = a + q[2]
            else:
                a = q[2] + a

print(a if tmp % 2 == 0 else a[::-1])

### FIXED CODE ###

from collections import deque
a = input()
a = deque(a)
n = int(input())
tmp = 0
for i in range(n):
    q = input().split()
    if len(q) == 1:
        tmp += 1
    elif len(q) == 3:
        if q[1] == '1':
            if tmp % 2 == 0:
                a.appendleft(q[2])
            else:
                a.append(q[2])
        elif q[1] == '2':
            if tmp % 2 == 0:
                a.append(q[2])
            else:
                a.appendleft(q[2])

print(''.join(a) if tmp % 2 == 0 else ''.join(a)[::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
doubly linked list
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
"""
# 9/10 ??§???????¶????????????????

from collections import namedtuple


class DualLinkList(object):
    def __init__(self):
        self.nil = namedtuple('Node', ['key', 'prev', 'next'])
        self.nil.next = self.nil
        self.nil.prev = self.nil

    def insert(self, key):
        x = namedtuple('Node', ['key', 'prev', 'next'])
        x.key = key
        x.next = self.nil.next
        self.nil.next.prev = x
        self.nil.next = x
        x.prev = self.nil

    def listSearch(self, key):
        cur = self.nil.next
        while cur != self.nil and cur.key != key:
            cur = cur.next
        return cur

    def deleteNode(self, t):
        if t == self.nil:
            return
        t.prev.next = t.next
        t.next.prev = t.prev
        # del t

    def deleteFirst(self):
        self.deleteNode(self.nil.next)

    def deleteLast(self):
        self.deleteNode(self.nil.prev)

    def deleteKey(self, key):
        self.deleteNode(self.listSearch(key))

    def get_keys(self):
        results = []
        cur = self.nil.next
        while cur != self.nil:
            results.append(cur.key)
            cur = cur.next
        return results

    def print(self):
        cur = self.nil.next
        while cur != self.nil:
            print(cur.key)
            cur = cur.next


def process_instructions(dll, insts):
    # line_count = 1
    for ins in insts:
        # print('processing line: {0}'.format(line_count))
        # line_count += 1
        try:
            code, key = ins.split()
        except ValueError:
            code = ins
        if code == 'insert':
            dll.insert(int(key))
        elif code == 'delete':
            dll.deleteKey(int(key))
        elif code == 'deleteFirst':
            dll.deleteFirst()
        elif code == 'deleteLast':
            dll.deleteLast()
        else:
            raise ValueError
    return dll.get_keys()



if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    data = [input() for x in range(num)]
    #data = []
    #with open('ALDS1_3_C_in9.txt') as f:  # ???????????????????????????
    #    for line in f:
    #       data.append(line.strip())
    #data = data[1:]

    # ??????????????????
    dll = DualLinkList()
    results = process_instructions(dll, data)

    # ???????????¨???
    print('{0}'.format(' '.join(map(str, results))))

### FIXED CODE ###

from collections import deque
n = int(input())
L = deque()

for i in range(n):
    cmdline = input().split()

    if cmdline[0] == "insert":
        L.appendleft(cmdline[1])
    elif cmdline[0] == "delete":
        try:
            L.remove(cmdline[1])
        except ValueError: pass
    elif cmdline[0] == "deleteFirst":
        L.popleft()
    elif cmdline[0] == "deleteLast":
        L.pop()

print(" ".join(L))
### BUGGY CODE ###

# 入力
N, Q = map(int, input().split(' '))
S = input()
ql = []
for _ in range(Q):
    l, r = map(int, input().split(' '))
    ql.append((l,r))

# 累積文字和の作成
cl = ['']
for char in S:
    cl.append(cl[-1] + char)

# クエリに対する出力
for i in range(Q):
    string = cl[ql[i][1]][ql[i][0]-1:]
    print(string.count('AC'))

### FIXED CODE ###

# coding:utf-8

# 入力
N, Q = map(int, input().split(' '))
S = input()
ql = [map(int, input().split(' ')) for _ in range(Q)]

# 累積和の作成
cl = [0, 0]
for i in range(N-1):
    if S[i] + S[i+1] == 'AC':
        cl.append(cl[-1]+1)
    else:
        cl.append(cl[-1])

# クエリに対する出力
for l, r in ql:
    print(cl[r] - cl[l])
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for i in range(m)]
memo = [0]*(n+1)

memo[0] = 1
if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
for i in range(2,n+1):
    if i in a:
        continue
    memo[i] = memo[i-1] + memo[i-2]

print(memo[n]%1000000007)

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for i in range(m)])
memo = [0]*(n+1)

memo[0] = 1
if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
for i in range(2,n+1):
    if i in a:
        continue
    memo[i] = (memo[i-1] + memo[i-2])%1000000007

print(memo[n])
### BUGGY CODE ###

S = input()

rem = {}
rem[0] = 1

moji = ''
MOD = 2019
cnt = 0

for i in range(1, len(S) + 1):
    moji = S[-i:]
    r = int(moji) % 2019
    if r in rem:
        cnt += rem[r]

    if r not in rem:
        rem[r] = 1
    else:
        rem[r] += 1

print(cnt)


### FIXED CODE ###

S = input()

num = 0

r_lst = [0] * 2019
r_lst[0] = 1
cnt = 0
for i, s in enumerate(S[::-1]):
    num = (num + pow(10, i, 2019) * int(s)) % 2019
    cnt += r_lst[num]

    r_lst[num] += 1


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

import sys
input = sys.stdin.readline


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

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            bottom = max(0, i-a)
            top = min(N, i+a+1)
            # B[bottom:top] = list(map(lambda x: x+1, B[bottom:top]))
            B[bottom] += 1
            B[top] -= 1
        for j in range(1, N):
            B[j] += B[j-1]

        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from numba import jit
import sys
input = sys.stdin.readline


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

    for _ in range(K):
        B = [0]*(N+1)
        for i, a in enumerate(A):
            B[max(0, i-a)] += 1
            B[min(N, i+a+1)] -= 1
        for j in range(1, N):
            B[j] += B[j-1]
        if A == B[:-1]:
            A = B[:-1]
            break
        A = B[:-1]

    ans = ' '.join(list(map(str, A)))
    print(ans)


if __name__ == '__main__':
    main()