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

def fuctorial(n):
    ret = 1
    while n > 0:
        ret *= n
        n -= 1
    return ret

def combination(n, k):
    return fuctorial(n) // (fuctorial(n-k) * fuctorial(k))


def main():
    N, K = map(int, input().split())
    MOD = 10**9+7
    for i in range(1,K+1):
        print(combination(N - K + 1, i) * combination(K - 1, i - 1) % MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def fuctorial(n):
    ret = 1
    while n > 0:
        ret *= n
        n -= 1
    return ret

def combination(n, k, MOD):
    return (fuctorial(n) // (fuctorial(n-k) * fuctorial(k)))%MOD


def main():
    N, K = map(int, input().split())
    MOD = 10**9+7
    for i in range(1, K + 1):
        if i > N - K + 1:
            print(0)
        else:
            print(combination(N - K + 1, i,MOD) * combination(K - 1, i - 1,MOD) % MOD)

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

n = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(n):
  for j in range(i + 1, n):
    result += (a[i] % (10**9 + 7)) * (a[j] % (10**9 + 7))
result = result % (10**9 + 7)
print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
sum_a = 0
result = 0
for i in range(n):
  sum_a += a[i]
for j in range(n):
  sum_a -= a[j]
  result += sum_a * a[j]
print(result % (10**9 + 7))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)
    ans=[0]*n
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        ans[p]+=x

    def dfs(v,p=-1):
        for u in E[v]:
            if u==p: continue
            ans[u]+=ans[v]
            dfs(u,v)

    dfs(0)
    print(*ans)

resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class EulerTour(object):
    def __init__(self,E,root=0):
        """
        E: list of int (adjacency list)
        root: int
        """
        n=len(E)
        self.__V=list(range(n))
        self.__E=E
        self.__begin=[0]*n
        self.__end=[0]*n
        self.__tour=[0]*(2*n-1)
        self.__k=0
        self.__dfs(root,-1)
        del self.__k

    def __dfs(self,v,p):
        self.__begin[v]=self.__k
        self.__tour[self.__k]=v
        self.__k+=1
        for u in self.__E[v]:
            if u==p: continue
            self.__dfs(u,v)
            self.__tour[self.__k]=v
            self.__k+=1
        self.__end[v]=self.__k

    @property
    def begin(self):
        return self.__begin

    @property
    def end(self):
        return self.__end

    @property
    def tour(self):
        return self.__tour

def resolve():
    # input
    n,q=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
        E[b].append(a)
    # build
    tree=EulerTour(E)
    # calculate
    imos=[0]*(2*n)
    for _ in range(q):
        p,x=map(int,input().split())
        p-=1
        imos[tree.begin[p]]+=x
        imos[tree.end[p]]-=x
    for i in range(2*n-1):
        imos[i+1]+=imos[i]
    # output
    print(*[imos[tree.begin[i]] for i in range(n)])
resolve()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
res = 0
while len(a) > 0:
    last = a[0]
    del a[0]
    res += 1
    i = 0
    while i < len(a):
        if last < a[i]:
            last = a[i]
            del a[i]
        else:
            i += 1
print(res)



### FIXED CODE ###

from bisect import bisect_left
from collections import deque

n = int(input())
a = [int(input()) for _ in range(n)]
res = deque([a[0]])
for x in a[1:]:
    if x <= res[0]:
        res.appendleft(x)
    else:
        res[bisect_left(res, x) - 1] = x

print(len(res))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
xy = [map(int, input().split()) for _ in range(Q)]
x, y = [list(i) for i in zip(*xy)]


def replace_list(num_list):
    num_list = [y[index] if j==i else j for j in num_list]
    return num_list

for index, i in enumerate(x):
    A = replace_list(A)
    print(sum(A))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
xy = [map(int, input().split()) for _ in range(Q)]
b, c = [list(i) for i in zip(*xy)]

sum_num = sum(A)
counter = collections.Counter(A)

for i in range(Q):
    sum_num -= counter[b[i]]*b[i] #counter[x]でxの個数をカウント
    sum_num += counter[b[i]]*c[i] #cで上書きされたので、c*counter[b]になる
    counter[c[i]] += counter[b[i]]
    counter[b[i]] = 0
    print(sum_num)
### BUGGY CODE ###

N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]


mx = -1e10
cnt = 0

for i in range(len(A)-1):
	if max(A[i+1:]) - A[i] > mx:
		mx = max(A[i+1:]) - A[i]
		cnt = 1

	elif max(A[i+1:]) - A[i] == mx:
		cnt += 1

print cnt

		
		
		


### FIXED CODE ###

N,T = [int(x) for x in raw_input().split(" ")]

A = [int(x) for x in raw_input().split(" ")]

mx = -1e10
cnt = 0
X = []

for i in range(len(A)):
	mx = max(A[-i-1],mx)
	
	dif = mx - A[-i-1]
	
	X.append(dif)



mxx = max(X)

for i in X:
	if i == mxx:
		cnt += 1

print cnt
### BUGGY CODE ###

k = int(input())
import itertools
def GCD(a,b):
    mx = max(a,b)
    mi = min(a,b)
    if(mx%mi == 0):
        return mi
    else:
        return GCD(mi,mx%mi)
total = 0
for i in list(itertools.product(list(range(1,k+1)),repeat=3)):
    a = int(i[0])
    b = int(i[1])
    c = int(i[2])
    #print(a,b,c)
    total += GCD(GCD(a,b),c)
print(total)

### FIXED CODE ###

k = int(input())
import itertools
def GCD(a,b):
    if(a%b == 0):
        return b
    else:
        return GCD(b,a%b)
total = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            total += GCD(GCD(a,b),c)
print(total)
### BUGGY CODE ###

import copy

N = int(input())

x_list = []
for i in range(N):
    x = int(input())
    x_list.append(x)

for i in range(len(x_list)):
    tmp_list = copy.deepcopy(x_list)
    tmp_list.pop(i)
    print(max(tmp_list))

### FIXED CODE ###

import copy

N = int(input())

x_list = []
for i in range(N):
    x = int(input())
    x_list.append(x)

max_value = max(x_list)

get_index = x_list.index(max(x_list))

tmp_list = copy.deepcopy(x_list)
tmp_list.pop(get_index)
without_max_value = max(tmp_list)

for i in range(len(x_list)):
    if i != get_index:
        print(max_value)
    else:
        print(without_max_value)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
jobs = []
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs.append([day, value])
jobs = sorted(jobs, lambda x: x[0])

ans = 0
hq = []
job_i = 0
for day in range(1, M+1):
    for job in list(jobs[job_i:]):
        if day < job[0]:
            break

        heapq.heappush(hq, - job[1])
        job_i += 1
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)


### FIXED CODE ###

import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

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

def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            for k in range(4): dp[i+1][j+1][k] = dp[i+1][j][k]
            v = max(dp[i][j+1])
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            if (i, j) in a:
                u = a[(i, j)]
                dp[i+1][j+1][1] = max([dp[i+1][j+1][1],  dp[i+1][j][0] + u,  v + u])
                dp[i+1][j+1][2] = max([dp[i+1][j+1][2], dp[i+1][j][1] + u ])
                dp[i+1][j+1][3] = max([dp[i+1][j+1][3], dp[i+1][j][2] + u ])

    return max(dp[R][C])

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


### FIXED CODE ###

def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

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

n, k = [int(x) for x in input().split()]

arr = []
for i in range(n):
    a, b = [int(x) for x in input().split()]
    arr += [a] * b

arr.sort()

print(arr[k-1])

### FIXED CODE ###

N, K = [int(x) for x in input().split()]
arr = [0] * (10**5+1)
for _ in range(N):
    a, b = [int(x) for x in input().split()]
    arr[a] += b

th = 0
for i in range(1, 10**5+1):
    if arr[i] != 0:
        th += arr[i]
    if th >= K:
        print(i)
        exit()
### BUGGY CODE ###

N,M = map(int,input().split())
P = list(map(int,input().split()))
L = [set(map(int,input().split())) for i in [None]*M]

LSET = L[:]
loop = True
while loop:
    loop = False
    LSET2 = []
    i = 0
    while i < len(LSET):
        j = i + 1
        tmp = LSET[i]
        if not tmp:
            i += 1
            continue
        while j < len(LSET):
            if  LSET[j] and not tmp.isdisjoint(LSET[j]):
                tmp |= LSET[j]
                loop = True
                LSET[j] = None
            j += 1
        LSET2.append(tmp)
        i += 1
    LSET = LSET2[:]

result = len([i for i in set(range(1,N+1)).difference(*LSET) if i == P[i-1]])
result += sum([ len({P[i-1] for i in s} & s )for s in LSET])
print(result)

### FIXED CODE ###

class UnionFind:
    def __init__(self,size):
        self.L = [{'parent':i,'rank':0} for i in range(size)]

    def find(self,x):
        if self.L[x]['parent'] != x:
            self.L[x]['parent'] = self.find(self.L[x]['parent'])
        return self.L[x]['parent']

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.L[x_root]['rank'] < self.L[y_root]['rank']:
            x_root,y_root = y_root,x_root

        self.L[y_root]['parent'] = x_root
        if self.L[x_root]['rank'] == self.L[y_root]['rank']:
            self.L[x_root]['rank'] += 1
    
    def __str__(self):
        return str([i['parent'] for i in self.L])

if __name__ == '__main__':
    N,M = map(int,input().split())
    P = list(map(int,input().split()))
    graph = UnionFind(N)
    for i in [None]*M:
        x,y = map(int,input().split())
        graph.union(x-1,y-1)
    count = 0
    for i,v in enumerate(P):
        if graph.find(i) == graph.find(v-1):
            count += 1
    print(count)
### BUGGY CODE ###

import heapq as hq

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = []
for s, t, x in STX:
  L.append([x, s - x, t - x])

L.sort(key = lambda x: x[1])
q = []
push = hq.heappush
pop = hq.heappop
cnt = 0
for i in range(Q):
  while cnt < len(L) and D[i] >= L[cnt][1]:
    push(q, L[cnt])
    cnt += 1
  while True:
    if q == []:
      print(-1)
      break
    t = pop(q)
    if t[2] > D[i]:
      print(t[0])
      push(q, t)
      break  

### FIXED CODE ###

import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(q, t)
        t = []
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()
### BUGGY CODE ###

import numpy as np

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

value = np.array(P)

ac = [v for i, v in enumerate(P) if v == np.minimum.accumulate(P)[i]]

print(len(ac))


### FIXED CODE ###

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

value = 10 ** 9
ans = 0
for v in P:
    if v < value:
        ans += 1
        value = v
print(ans)
### BUGGY CODE ###

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

graph = [[] for i in range(N)]

for i in range(M):
  u,v = map(int,input().split())
  graph[u - 1].append(v - 1)

S,T = map(int,input().split())
S -= 1
T -= 1

from collections import deque
q = deque([])
q.append([S, 0, 0])

seen = set()

while q:
  v,cost,step = q.popleft()
  if step == 0:
    if v == T:
      print(cost)
      break
    if v in seen:
      continue
    seen.add(v)
    cost += 1
    step = 3
  for u in graph[v]:
    q.append([u, cost, step - 1])
else:
  print(-1)

### FIXED CODE ###

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

graph = [[] for i in range(N)]

for i in range(M):
  u,v = map(int,input().split())
  graph[u - 1].append(v - 1)

S,T = map(int,input().split())
S -= 1
T -= 1

from collections import deque
q = deque([])
q.append([S, 0, 0])

seen = [[False] * 3 for i in range(N)]

while q:
  v,cost,step = q.popleft()
  if seen[v][step]:
    continue
  seen[v][step] = True
  if step == 0:
    if v == T:
      print(cost)
      break
    cost += 1
    step = 3
  for u in graph[v]:
    q.append([u, cost, step - 1])
else:
  print(-1)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    H, N = map(int, input().split())
    A = [None] * N
    B = [None] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    #1次元DPに書き換え
    INF = 10**12
    dp = [INF] * (H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)],dp[j]+B[i])
    print(dp[H])

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, N = map(int, input().split())
    A = [None] * N
    B = [None] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    INF = 10**12
    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(H+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min(j+A[i],H)] = min(dp[i+1][min(j+A[i],H)],dp[i+1][j]+B[i])
    print(dp[N][H])

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

import statistics
N = int(input())
X = list(map(int,input().split()))
for i in range(N) :
    x = X[0]
    X.pop(0)
    print(statistics.median(X))
    X.append(x)



### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
Y = X.copy()
X = sorted(X)
bigger = X[N//2]
smaller = X[N//2-1]

for i in range(N) :
    if Y[i] >= bigger :
        print(smaller)
    else :
        print(bigger)
### BUGGY CODE ###

K = int(input())
import math  
from functools import reduce
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans = ans + reduce(math.gcd,[a,b,c]) 
print(ans)        

### FIXED CODE ###

K = int(input())
from math import gcd
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans = ans + gcd(gcd(a,b),c)
print(ans)
### BUGGY CODE ###

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

water = A[:]
#print(water)

ans = []
for x in range(0, max(water[0], water[-1])*2+1, 2):
    #print(x)
    ans = [x]
    for i, a in enumerate(water):
        y = 2*a - x
        #print(y)
        if y % 2 == 1:
            break
        ans.append(y)
        x = y
    if len(ans) == N+1 and ans[0] == ans[-1]:
        #print(len(ans), N)
        break
print(' '.join(list(map(str, ans[:-1]))))

### FIXED CODE ###

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

water = A[:]
#print(water)

ans = []
x = 0
#print(x)
ans = [x]
for i, a in enumerate(water):
    y = 2*a - x
    #print(y)
    ans.append(y)
    x = y
#print(ans, sum(ans))

x = (ans[0] + ans[-1]) // 2
ans = [x]
for i, a in enumerate(water):
    y = 2*a - x
    #print(y)
    ans.append(y)
    x = y
#print(ans, sum(ans))





print(' '.join(list(map(str, ans[:-1]))))
### BUGGY CODE ###

N=input()
cost={}

org=[[float("inf") for i in range(N)] for _ in range(N)]
for i in range(N):
	A=map(int, raw_input().split())
	for j in range(N):
		org[i][j]=A[j]
		if j>i:
			cost[(i,j)]=A[j]


for param in range(-1,len(cost)-N+1):

	cost_sel=sorted(cost.items(), key=lambda x: x[1])[:N+param]

	#Initialize
	dp=[[float("inf") for i in range(N)] for _ in range(N)]
	for i in range(N): dp[i][i]=0

	for i,j in cost_sel:
		dp[i[0]][i[1]]=j
		dp[i[1]][i[0]]=j

	#Warshall-Floyd
	for k in range(N):
		for x in range(N):
			for y in range(N):
				dp[x][y]=min(dp[x][y], dp[x][k]+dp[k][y])

	#print dp
	if org==dp:
		print sum( [x[1] for x in cost_sel] )
		quit()
else:
	print -1
		

### FIXED CODE ###

import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	#print i,j,A[i], A[j], np.min(A[i]+A[j]),d1
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [ [0 for _ in range(W+1)] for _ in range(N) ]

    dp[0][w[0]] = v[0]

    for i in range(1,N):
        for j in range(0,W+1):
            if j - w[i] >= 0:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i])
            else:
                dp[i][j] = dp[i-1][j]

    print(dp[-1][-1])
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import defaultdict


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

    for i in range(1,N+1):
        for j in range(W+1):
            dp[i][j] = dp[i-1][j]
            if j >= w[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])
    print(dp[N][W])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

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

import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')

from math import log
def log2(x): return log(x, 2)


class Doubling(object):

    def __init__(self, N, K, next0):
        """
        ダブリングのメモ構築 O(NlogK)
        :param N: 解の存在空間の大きさ
        :param K: K個先までのステップを考慮する
        :param next0: i番目の要素の1個先の番号を要素として持つリスト
                      次の要素が存在しない場合には-1を要素として保持する
        """
        next = [[0] * N for _ in range(int(log2(K)) + 1)]
        next[0] = next0
        for k in range(int(log2(K))):
            for i in range(N):
                if next[k][i] == -1:
                    # 2^k個次に要素が無い時、当然2^(k+1)個次にも要素はない
                    next[k + 1][i] = -1
                else:
                    # i番目の要素の2^(k+1)個次の要素 := next[k][i](i番目の要素の2^k個次の要素)の2^k個先
                    next[k + 1][i] = next[k][next[k][i]]
        self.next = next

    def query(self, p, K):
        """
        p番目の要素のK個次の要素を求める O(logK)
        """
        for i in reversed(range(int(log2(K)) + 1)):
            if p == -1:
                return p
            if (K >> i) & 1:
                p = self.next[i][p]
        return p


S = input()

times = 10 ** 100
n0 = [i + 1 if c == 'R' else i - 1 for i, c in enumerate(S)]
d = Doubling(len(S), times, n0)

ans = [0] * len(S)
for i in range(len(S)):
    ans[d.query(i, times)] += 1
print(' '.join(str(x) for x in ans))


### FIXED CODE ###

S = input()

lst = list()
rev = False
r = 0
l = 0
start = 0
for i in range(len(S)):
    c = S[i]
    if rev and c == 'R':
        lst.append((start, r, l))
        r = 1
        l = 0
        start = i + 1
        rev = False
        continue
    if c == 'R':
        r += 1
    elif c == 'L':
        rev = True
        l += 1
lst.append((start, r, l))

ans = list()
for start, r, l in lst:
    for _ in range(r - 1):
        ans.append(0)

    a = 0
    b = 0
    if r % 2 != 0:
        a += 1
    a += r // 2
    b += r // 2
    if l % 2 != 0:
        b += 1
    a += l // 2
    b += l // 2
    ans.append(a)
    ans.append(b)

    for _ in range(l - 1):
        ans.append(0)

print(' '.join([str(x) for x in ans]))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i not in a:
    b[i]+=b[i-1]
    if i>1:b[i]+=b[i-2]
  else:
    b[i]=0
  b[i]%=(10**9+7)
 
 
print(b[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
a = set(int(input()) for _ in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))