Harryxun/stf_run huggingface dataset:
N, K = map(int, input().split())
 
def fact(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * fact(n-1)

def nCr(n, r):
    return fact(n) // fact(n - r) * fact(r)
 
for j in range(K):
  if (K+j)>N:
    print(0)
  else:
    x = (nCr((K-1), j) * nCr(N-K+1, j+1))
    if (x > (10**9+7)):
         print(x%(10**9+7))
    else:
         print(x)

### FIXED CODE ###

N, K = map(int, input().split())
from operator import mul
from functools import reduce
 
def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
 
for j in range(K):
  if (K+j)>N:
    print(0)
  else:
    x = (nCr((K-1), j) * nCr(N-K+1, j+1))
    if (x > (10**9+7)):
         print(x%(10**9+7))
    else:
         print(x)
import math
N,A,B=map(int,input().split())
v=list(map(int,input().split()))
a=v.sort()[-A:]
print(sum(a)/A)
b=v.count(a[0])
c=a.count(a[0])
if c!=A:
    print(math.factorial(b)//(math.factorial(c)*math.factorial(b-c)))
else:
    l=[]
    i=min([b-c,B-A])
    for k in range(0,i+1):
        l.append(math.factorial(b)//(math.factorial(c+k)*math.factorial(b-c-k)))
    print(sum(l))

### FIXED CODE ###

a,b=input().split()
print((int(a)+int(b))%24)
s = input()
if s[2] == s[3] and s[4] == s[5]:
  print("Yes")
else:
  print("No)

### FIXED CODE ###

s = input()
if s[2] == s[3] and s[4] == s[5]:
  print("Yes")
else:
  print("No")
n = int(input())
edgeList = []


def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], getRoot(i), getRoot(j)])
rootList = [-1 for i in range(n)]
sumLength = 0
edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

### FIXED CODE ###

n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], i, j])
rootList = [-1]*n
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        

edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)
# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + mod_list[:min(counter, N - 1)]
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:counter])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, X, M = map(int, input().split())

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:N - 1])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)
n, q = map(int, input().split())
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
adds = [0]*(n+1)
for _ in range(q):
    p, x = map(int, input().split())
    adds[p] += x

res = [0]*(n+1)

def add_x(p, x):
    res[p] += x
    for child in tree[p]:
        add_x(child, x)

for i in range(1, n+1):
    add_x(i, adds[i])

print(' '.join(list(map(str, res[1:]))))

### FIXED CODE ###

import sys
from heapq import *
sys.setrecursionlimit(10**8)

input = sys.stdin.readline

tree = [[] for _ in range(200001)]
res = [0]*200001

def dfs(p, pre):
    for child in tree[p]:
        if child == pre: continue
        res[child] += res[p]
        dfs(child, p)

def main():
    """ main """
    N, Q = map(int, input().split())
    for _ in range(N-1):
        a,b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    for _ in range(Q):
        p,x = map(int, input().split())
        res[p] += x
    dfs(1, 0)

    print(*res[1:N+1])

if __name__ == '__main__':
    main()
x =map(int,input())
x = sorted(x, reverse=True)

print(x[0] * 10 + x[1] + x[2])


### FIXED CODE ###


x =map(int,input().split())
x = sorted(x, reverse=True)

print(x[0] * 10 + x[1] + x[2])
import math

def f(n):
  s = ""
  if n == 0:
    return 0
  for i in reversed(range(int(math.log2(n))+1)):
    if i == 0:
      s += "1" if ((n-1)//2)%2 == 0 else "0"
    else:
      s += "1" if (n//(2**i))%2 + (n+1)%2 == 2 else "0"
  return int(s,2)

a,b = map(int,input().split())
print( f(a-1) ^ f(b) )

### FIXED CODE ###

import math

def f(n):
  s = ""
  if n <= 0:
    return 0
  for i in reversed(range(int(math.log2(n))+1)):
    if i == 0:
      s += "1" if ((n-1)//2)%2 == 0 else "0"
    else:
      s += "1" if (n//(2**i))%2 + (n+1)%2 == 2 else "0"
  return int(s,2)

a,b = map(int,input().split())
print( f(a-1) ^ f(b) )
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


li = []
n = int(input())
for i in range(5):
    li.append(int(input()))
if n == min(i):
    print(5)
else:
    print(5 + n // min(li))

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


li = []
n = int(input())
for i in range(5):
    li.append(int(input()))
if n <= min(li):
    print(5)
else:
    if n % min(li) == 0:
        print(5 + n // min(li) -1)
    else:
        print(5 + n // min(li))
import math

s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=int(s[1])
for i in range(s[1]):
  for j in range(s[0]):
    if max(t)==t[j] and 0<b:
      t[j]=math.floor(t[j]/2)
      b=b-1
    elif: b<=0:
        break
for l in range(s[0]):
  a=a+t[l]
print(a)

### FIXED CODE ###

import math
 
s=list(map(int,input().split()))
t=list(map(int,input().split()))
a=0
b=0
c=0
d=s[1]
t.sort(reverse=True)
if s[0]==1:
  for i in range(s[1]):
    t[0]=math.floor(t[0]/2)
else:
  c=t[0]/2
  for j in range(s[1]):
    for l in range(s[0]):
      if d>0:
        if c<t[l]:
          t[l]=math.floor(t[l]/2)
          d=d-1
        else:
            t.sort(reverse=True)
            c=t[0]/2
            break
      else:
        break
e=sum(t)
print(e)
N=int(input())
INL=list(map(int,input().split()))

swp = 0
for i in range(0, N):
    if i+1 == INL[i]:
        INL[i], INL[i+1] = INL[i+1], INL[i]
        swp += 1

print(swp)


### FIXED CODE ###

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

swp = 0
for i in range(0, N-1):
    if i+1 == INL[i]:
        INL[i] = INL[i] ^ INL[i+1]
        INL[i+1] = INL[i] ^ INL[i+1]
        INL[i] = INL[i] ^ INL[i+1]
        swp += 1

if INL[N-1] == N:
    INL[N-1], INL[N-2] = INL[N-2], INL[N-1]
    swp += 1

print(swp)
H, W, M = list(map(int, input().split()))

targets = set()
row = [0]*H
col = [0]*W
bomb = [[0]*W for _ in range(H)]

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    bomb[h][w] = 1

r_max = max(row)
c_max = max(col)
ans = 0
# print([h for h in range(H) if row[h] == r_max])
# print([w for w in range(W) if col[w] == c_max])
for h in [h for h in range(H) if row[h] == r_max]:
    for w in [w for w in range(W) if col[w] == c_max]:
        # print(r_max + c_max - 1 if (h, w) in targets else 0)
        if bomb[h][w]:
            ans = max(ans, r_max + c_max - 1)
        else:
            ans = max(ans, r_max + c_max)
print(ans)



### FIXED CODE ###

H, W, M = list(map(int, input().split()))

targets = set()
row = [0]*H
col = [0]*W

for _ in range(M):
    h, w = list(map(lambda x: int(x) - 1, input().split()))
    row[h] += 1
    col[w] += 1
    targets.add((h, w))

r_max = max(row)
c_max = max(col)
ans = 0

maxed_h = set([h for h in range(H) if row[h] == r_max])
maxed_w = set([w for w in range(W) if col[w] == c_max])
bomb_option_sites_n = len(maxed_h)*len(maxed_w)
targets_on_bomb_option = 0
for th, tw in targets:
    if th in maxed_h and tw in maxed_w:
        targets_on_bomb_option += 1

if bomb_option_sites_n == targets_on_bomb_option:
    print(r_max + c_max - 1)
else:
    print(r_max + c_max)
x = input
x = x*x*x
print(x)


### FIXED CODE ###

x = int(input())
print(x*x*x)
listnum = int(input())
string = input()

halfnum = listnum // 2
halfstr = string[0:halfnum]
if string == halfstr + halfstr:
	print('Yes')
else:
	print('No')

### FIXED CODE ###

r = int(input())
print(r*r)
# 2019/09/28
from fractions import gcd

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


# 約数列挙

def divisors(n):
    div=[]
    if n%2==0:div.append(2)
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            if i%2:
                div.append(i)
                if i!=n//i and n//i%2:
                    div.append(n//i)
    # div.sort()
    return div

diva=divisors(a)
divb=divisors(b)
div=set()
for aa,bb in zip(diva,divb):
    if aa in divb:
        div.add(aa)
    if bb in diva:
        div.add(bb)

# エラトステネスの篩
def sieve(n):
    end=int(pow(n,0.5))+1
    is_prime=[True]*(n+1) 
    is_prime[0]=False
    is_prime[1]=False

    for i in range(2,end):
        if not is_prime[i]:continue
        for j in range(i*2,n+1,i):
        #for j in range(i*(i|0),n+1,i):
            is_prime[j]=False
    return [i for i in range(n+1) if is_prime[i]]

prime=sieve(max(div))

cnt=1
res=[]
for e in div:
    if e in prime:
        res.append(e)


cnt+=len(res)
for i in div:
    if i==1:continue
    for j in res:
        if j==1:continue
        if i==j:continue
        if i in res and j in res:continue
        if gcd(i,j)==1:continue
        else:break
        cnt+=1
print(cnt)

### FIXED CODE ###

# 2019/09/30

from fractions import gcd

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

g=gcd(a,b)


def trial_div(n):
    from collections import Counter
    
    prime=Counter()

    for i in range(2,int(pow(n,0.5)+2)):
        while n%i==0:
            n//=i
            prime[i]+=1
    if n>1:prime[n]+=1
    
    return prime


res=trial_div(g)
print(1+len(res))
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
S = str(input())
S = S + "2"
d1 = []
d0 = []
k = S[0]
if k=="0":
    d1.append(0)
cou = int(1)
for i in range(N):
    if S[i]!=S[i+1]:
        if S[i]=="0":
            d0.append(cou)
        if S[i]=="1":
            d1.append(cou)
        cou = int(1)
    else:
        cou +=1

#print(d1)
#print(d0)

ansC = []
t = 2*K+1
newN = len(d1)
if len(d1)==1 or d0==[] or K>=N//2+1:
    ansC.append(N)

if newN!=len(d0):
    d0.append(0)
    d0.append(0)
sumd1 = [0]*(newN+t+5)
sumd0 = [0]*(newN+t+5)
for i in range(newN):
    sumd1[i+1] = d1[i]
    sumd0[i+1] = d0[i]
for i in range(newN+1):
    sumd1[i+1] += sumd1[i]
    sumd0[i+1] += sumd0[i]

#for i in range(max(newN-K+1,K)):
if ansC==[] and (newN - K + 1)>=1:
    for i in range(newN - K + 1):
        ans = (sumd1[i + K + 1] - sumd1[i]) + (sumd0[i + K] - sumd0[i])
        ansC.append(ans)

print(max(ansC))
#print(ansC)
#print(sumd1)
#print(sumd0)

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, K = LI()
S = str(input())
S = S + "2"
d1 = []
d0 = []
k = S[0]
if k=="0":
    d1.append(0)
cou = int(1)
for i in range(N):
    if S[i]!=S[i+1]:
        if S[i]=="0":
            d0.append(cou)
        if S[i]=="1":
            d1.append(cou)
        cou = int(1)
    else:
        cou +=1

#print(d1)
#print(d0)

ansC = []
t = 2*K+1
newN = len(d1)
if len(d1)==1 or d0==[] or K>=N//2+1:
    ansC.append(N)

if newN!=len(d0):
    d0.append(0)
    d0.append(0)
sumd1 = [0]*(newN+t+5)
sumd0 = [0]*(newN+t+5)
for i in range(newN):
    sumd1[i+1] = d1[i]
    sumd0[i+1] = d0[i]
for i in range(newN+1):
    sumd1[i+1] += sumd1[i]
    sumd0[i+1] += sumd0[i]

#for i in range(max(newN-K+1,K)):
if ansC==[] and (newN - K + 1)>=1:
    for i in range(newN - K + 1):
        ans = (sumd1[i + K + 1] - sumd1[i]) + (sumd0[i + K] - sumd0[i])
        ansC.append(ans)
else:
    ansC.append(N)
print(max(ansC))
A, B = [int(input()) for _ in range(2)]
 
P = A + B
M = A - B
T = A * B
 
list = [P, M, T]
print(max(list))

### FIXED CODE ###

A, B = map(int, input().split())

P = A + B
M = A - B
T = A * B

print(max(P, M, T))
input_line = raw_input()

idx_start = 0
while input_line[idx_start] != 'A':
    idx_start += 1

idx_end = len(input_line)
while input_line[idx_end-1] != 'Z':
    idx_end -= 1

print(idx_end - idx_start)


### FIXED CODE ###

input_line = raw_input()

idx_start = 0
while input_line[idx_start] != 'A':
    idx_start += 1

idx_end = len(input_line)
while input_line[idx_end-1] != 'Z':
    idx_end -= 1

print(idx_end - idx_start)
s, t = input().split()
a, b = map(int, input().split())
u = input()
if u == s:
    print(str(a)-1+" "+str(b))
else:
    print(str(a)+" "+str(b-1))


### FIXED CODE ###

s, t = input().split()
a, b = map(int, input().split())
u = input()
if u == s:
    print(str(a-1)+" "+str(b))
else:
    print(str(a)+" "+str(b-1))
n, m = list(map(int, input().split(" ")))

ds = [x for x in range(1, m**.5+1) if m%x==0]
ds = ds + [m%x for x in ds]
ds = [x for x in ds if x<=m//n]
print(max(ds))

### FIXED CODE ###

N, M = list(map(int, input().split(" ")))
def solv(N, M):
    d = M//N
    for i in range(d+1)[::-1]:
        if M%i == 0:
            return i
print(solv(N, M))
N, M = [int(x) for x in input().split(' ')]
edges = []
for _ in range(M):
    edges.append([int(x) - 1 for x in input().split(' ')])
res = [str(N * (N-1) // 2)]
init = N * (N-1) // 2
f = list(range(N))
cnt = [1] * N
def find(x):
    if x != f[x]:
        f[x] = find(f[x])
    return f[x]
for i in range(M-1, 0, -1):
    a, b = edges[i]
    fx, fy = find(a), find(b)
    if fx == fy:
        res.append(str(init))
    else:
        f[fy] = fx
        pre = cnt[fx] * (cnt[fx] - 1) // 2 + cnt[fy] * (cnt[fy] - 1) // 2
        cnt[fx] += cnt[fy]
        # print(a, b, f, cnt)
        init = init - cnt[fx] * (cnt[fx]-1) // 2 + pre
        res.append(str(init))
print('\n'.join(res[::-1]))

### FIXED CODE ###

N, M = [int(x) for x in input().split(' ')]
edges = []
for _ in range(M):
    edges.append([int(x)-1 for x in input().split(' ')])
res = [str(N * (N-1) // 2)]
init = N * (N-1) // 2
f = list(range(N))
cnt = [1] * N
def find(x):
    if x != f[x]:
        f[x] = find(f[x])
    return f[x]
for i in range(M-1, 0, -1):
    a, b = edges[i]
    fx, fy = find(a), find(b)
    if fx == fy:
        res.append(str(init))
    else:
        
        pre = cnt[fx] * (cnt[fx] - 1) // 2 + cnt[fy] * (cnt[fy] - 1) // 2
        if cnt[fx] < cnt[fy]:
            f[fx] = fy
            cnt[fy] += cnt[fx]
            init = init - cnt[fy] * (cnt[fy]-1) // 2 + pre
        else:
            f[fy] = fx
            cnt[fx] += cnt[fy]
            init = init - cnt[fx] * (cnt[fx] - 1) // 2 + pre
        res.append(str(init))
print('\n'.join(res[::-1]))
n,a,b=map(int,input().split())
print(min(n*a,b)

### FIXED CODE ###

n,a,b=map(int,input().split())
print(min(n*a,b))
for mn in range(n):
    a=input()# String1 in the pair
    b=input()#String2 in the pair
    la=[]
    lb=[]

    for i in range(max(len(a),len(b))):#creating lists with all possible elements by slicing off the characters
        la.append(a[i:])
        lb.append(b[i:])

    if len(a)>len(b):#removes empty elements
        lb=[x for x in lb if x!='']
    else:
        la=[x for x in la if x!='']

    while True:#Create empty list for sorting the 0th elements of 'la' nd 'lb'
        temp=[]
        temp.append(la[0])
        temp.append(lb[0])
        temp=sorted(temp)
        print(temp[0][0],end='')#print the 1st character

        if(temp[0] in la):#removing the element after printing the first character
            la.pop(0)
        else:
            lb.pop(0)

        if len(la)==0:#breaks the while loop if a list gets empty
            print(temp[1],end='')
            break
        elif len(lb)==0:
            print(temp[1],end='')
            break

### FIXED CODE ###

A,B=input().split()
print(B+A)
# aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
n = input()
h = [int(i) for i in input().split()]

max = 0
i = 0
y = 1
for i in range(n):
    if h[i] > max:
        max = h[i]
    elif h[i] < max-1:
        y = 0
    
if y==1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

n = input()
h = [int(i) for i in input().split()]

max = 0
i = 0
y = 1
for i in range(int(n)):
    if h[i] > max:
        max = h[i]
    elif h[i] < max-1:
        y = 0
    
if y==1:
    print("Yes")
else:
    print("No")
n=int(input())
ans=0
a=0;b=0;ab=0
for i in range(n):
  s=input()
  ans+=s.count("AB")
  if s[0]=="B":
    b+=1
    if s[-1]=="A":
      ab+=1
      b-=1
  elif s[-1]=="A":
    a+=1
if a+b==0:
    print(ans+ab-1)
else:
    print(ans+min(a,b)+ab)


### FIXED CODE ###

n,k = map(int,input().split())
print(n-k+1)
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
p = list(map(float, input().split()))

import numpy as np
dp = np.full(N+1, 0, dtype=np.float64)
dp[0] = 1
n_p = np.array(p)

for i in range(N):
    tmp      = np.zeros_like(dp)
    tmp[1:]  = dp[:-1] * n_p[i]
    tmp[:-1]+= dp[:-1] * (1-n_p[i])
    dp = tmp

ans = np.sum(dp[N//2+1:])
print(ans)

# for i in range(1, 1+N): # timestep
#     for j in range(0, 0+i): # pos
#         dp[j] = dp[
#     # kdp[:i] a

# suml = [[1 for x in range(round+1)] for round in range(N+1)]
# 
# for e,p in enumerate(P):
#     for (es, s),_ in zip(enumerate(suml[e]), range(e+1)):
# 
#         if (es == 0):
#             suml[e+1][es]   = suml[e][es] * (1-p)
#         else:
#             suml[e+1][es]   += suml[e][es] * (1-p)
# 
#         suml[e+1][es+1] = suml[e][es] * p
# 
# 
# sumA = suml[N][:len(suml[N])//2-1:-1]
# sumA = sum(sumA)
# print(sumA)


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
p = list(map(float, input().split()))

import numpy as np
dp = np.full(N+1, 0, dtype=np.float64)
dp[0] = 1
n_p = np.array(p)

for i in range(N):
    tmp      = np.zeros_like(dp)
    tmp[1:]  = dp[:-1] * n_p[i]
    tmp[:-1]+= dp[:-1] * (1-n_p[i])
    dp = tmp

ans = np.sum(dp[N//2+1:])
print(ans)

# for i in range(1, 1+N): # timestep
#     for j in range(0, 0+i): # pos
#         dp[j] = dp[
#     # kdp[:i] a

# suml = [[1 for x in range(round+1)] for round in range(N+1)]
# 
# for e,p in enumerate(P):
#     for (es, s),_ in zip(enumerate(suml[e]), range(e+1)):
# 
#         if (es == 0):
#             suml[e+1][es]   = suml[e][es] * (1-p)
#         else:
#             suml[e+1][es]   += suml[e][es] * (1-p)
# 
#         suml[e+1][es+1] = suml[e][es] * p
# 
# 
# sumA = suml[N][:len(suml[N])//2-1:-1]
# sumA = sum(sumA)
# print(sumA)
from math import *

def fib(n):
    return ((1+sqrt(5))**(n+1)  -  (1-sqrt(5))**(n+1)) // (2**(n+1)*sqrt(5))


def how_many_ways(lst_of_broken_steps,goal):

    for i in range(len(lst_of_broken_steps)-1):#連続しているbrokenステップがあった時
        if lst_of_broken_steps[i]+1==lst_of_broken_steps[i+1]:
            return 0
    
    #1回目のbrokenステップの処理
    ans = fib(lst_of_broken_steps[0]-1)
    print(ans)
  

    for i in range(1,len(lst_of_broken_steps)):#2回目以降のbrokenステップの処理
        ans *= fib((lst_of_broken_steps[i]-1)-(lst_of_broken_steps[i-1]+1))
        ans = ans%1000000007
        print(ans)#けす
    

    #最後のbrokenステップの処理の後からゴールまで
    ans *= fib(goal-(lst_of_broken_steps[-1]+1))

    return ans % 1000000007


    
goal,n = map(int,input().split())
lst_of_broken_steps = []
for i in range(n):
    lst_of_broken_steps.append(int(input()))

print(int(how_many_ways(lst_of_broken_steps,goal)))

### FIXED CODE ###

n,m = map(int,input().split())
brokensteps = set([int(input()) for x in range(m)])
dp = [0] * (n+1)
for i in range(n+1):
    if i in brokensteps:
        dp[i] = 0
        continue
    
    elif i <= 1:
        dp[i] = 1

    else:
        dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)

print(dp[n])
N = int(input())
S = list(input())

CNT = []
c = 0
for s in S:
  if s == "E":
    c += 1
  CNT.append(c)
  
ans = N + 10
mn = N + 10
for i in range(N):
  c = 0
  if i > 0:
    c += i - 1 - CNT[i-1]
  if i < N - 1:
    c +=  N - i - 1 - (CNT[N] - CNT[i+1])
    
  if c < mn:
    ans = i+1

print(ans)
    

  

### FIXED CODE ###

N = int(input())
S = list(input())

EAST = []
WEST = []
e = 0
w = 0
for s in S:
  if s == "E":
    e += 1
  else:
    w += 1
  EAST.append(e)
  WEST.append(w)
  
ans = N - 1
for i in range(N):
  c = 0
  if i > 0:
    c += WEST[i-1]
  if i < N - 1:
    c += EAST[N-1] - EAST[i]
  
  ans = min(c,ans)

print(ans)
def insert(S, string):
    S.append(string)

def find(S, string):
    cnt = 0
    for i in range(len(S)):
        cnt = cnt + 1
        if S[i] == string:
            print 'yes'
            break
        elif cnt == len(S):
            print 'no'

n = input()

S = []

for i in range(n):
    tmp1, tmp2  = map(str,raw_input().split())
    if tmp1 == 'insert':
        insert(S, tmp2)
    elif tmp1 == 'find':
        find(S, tmp2)
    else:
        print 'error!'

### FIXED CODE ###

def insert(S, string):
    S.add(string)

def find(S, string):
    if string in S:
        print 'yes'
    else:
        print 'no'

n = input()

S = set()

for i in range(n):
    tmp1, tmp2  = map(str, raw_input().split())
    if tmp1 == 'insert':
        insert(S, tmp2)
    elif tmp1 == 'find':
        find(S, tmp2)
    else:
        print 'error!'
n, m = map(int, input().split())

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

for i in range(m):
    x,y = map(int, input().split())
    xy_dict[x].append(y)

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    # global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

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

xy_dict = {}
for i in range(1,n+1):
    xy_dict[i] = []

for i in range(m):
    x,y = map(int, input().split())
    xy_dict[x].append(y)

dp = [-1]*(n+1)
dp[0] = 0

def get_longest(x):
    global dp

    if( dp[x] >= 0):
        return dp[x]
    else:
        y_list = xy_dict[x]
        temp_max = 0
        for y in y_list:
            temp_max = max(temp_max, get_longest(y)+1)

        dp[x] = temp_max
        return temp_max

ans = 0
for i in range(1,n+1):
    ans = max(ans, get_longest(i))

print(ans)