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

#!/usr/bin/env python3
import sys

def solve(S: int):
    ans = []

    S2 = 10**9
    if S <= S2:
        ans = [0,0,1,0,0,S]
    else:
        for i in range(S2,1,-1):
            if S % i == 0:
                ans = [0,0,i,0,0,S//i]

    print(" ".join([str(i) for i in ans]))
    return


# 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()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(S: int):
    ans = []

    S2 = 10**9
    if S <= S2:
        ans = [0,0,1,0,0,S]
    else:
        A = min(int(S**0.5) + 1,10**9)

        B = A**2 - S
        ans = [0,0,A,B,1,A]

    print(" ".join([str(i) for i in ans]))
    return


# 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()
    S = int(next(tokens))  # type: int
    solve(S)

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

import numpy as np

#N = 39
#S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"
N=int(input())
S=input()
r = len(S.replace("G", "").replace("B", ""))
g = len(S.replace("R", "").replace("B", ""))
#b = len(S.replace("R", "").replace("G", ""))
b = N - r - g
 
ans = r * g * b
 
for i in range(N):
    for k in [N - k_ - 1 for k_ in range(N)]:
        tar_j = i + k
        if (tar_j > 2 * i) & (tar_j < 2 * k):
            if np.mod(tar_j, 2) == 0:
                j = int(tar_j / 2)
                s = S[i] + S[j] + S[k]
                if ("R" in s) & ("G" in s) & ("B" in s):
                    ans -= 1
        else:
            break
print(ans)


### FIXED CODE ###


#S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"# * 1000
#N = len(S)

N=int(input())
S=input()
r = len(S.replace("G", "").replace("B", ""))
g = len(S.replace("R", "").replace("B", ""))
b = N - r - g
 
ans = r * g * b
 
is_break = False
for i in range(N):
    for j in range(i, int((N+i)/2 + 1)):
        k = 2 * j - i
        if k < N:
            s = S[i] + S[j] + S[k]
            if ("R" in s) & ("G" in s) & ("B" in s):
                    ans -= 1

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

from collections import defaultdict, deque

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

strList = defaultdict(deque)

for leng in range(N // 2 + 1):
    for left in range(N - leng + 1):
        sub = S[left: left + leng]
        strList[sub].append(left)

ans = 0
for sub, leftList in strList.items():
    leng = len(sub)
    if leftList[0] + leng <= leftList[-1]:
        ans = max(ans, leng)

print(ans)


### FIXED CODE ###

from collections import deque

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

def isOk(leng):
    hashList = set()
    que = deque([])
    for left in range(N - leng + 1):
        hs = hash(S[left: left + leng])
        if hs in hashList:
            return True
        que.append(hs)
        if len(que) >= leng:
            hashList.add(que.popleft())
    return False

ok = 0
ng = N

while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

a = []

n,k = map(int, input().split())
for x in range(k):
  a.append(0)
q = input()

p = 0
c = 0
mx = 0

for i in range(n-1):
  c = c+1  
  if q[i] == q[i+1]:
    lalala = 1

  elif (int(q[i]) == 1) & (int(q[i+1]) == 0) :
    
    for x in a:
      p = p + x
    if mx < p+c:
      mx = p+c
    p = 0
    
  elif (int(q[i]) == 0) & (int(q[i+1]) == 1):
    a.append(c)
    a.pop(0)
    c = 0
for x in a:
  p = p + x
if int(q[n-1]) == 1:
  if mx < p+c+1:
    mx = p+c+1
else:
  p=0
  a.pop(0)
  for x in a:
    p = p + x
  if mx < p+c+1:
    mx = p+c+1
  


print(mx)

### FIXED CODE ###

a = []

n,k = map(int, input().split())
for x in range(k+1):
  a.append(0)
q = input()

p = 0
c = 0
mx = 0

for i in range(n-1):
  p = p+1
  c = c+1  
  if q[i] == q[i+1]:
    lalala = 1

  elif (int(q[i]) == 1) & (int(q[i+1]) == 0) :
    p = p-a[0]
    if p > mx:
      mx = p
    
  elif (int(q[i]) == 0) & (int(q[i+1]) == 1):
    a.pop(0)
    a.append(c)
    c = 0

if int(q[n-1]) == 1:
  if p+1- a[0]> mx:
    mx = p +1 - a[0]
else:
  if p+1 -a[1] > mx:
    mx = p  -a[1] +1
  
  


print(mx)
### BUGGY CODE ###

S = input()
Q = int(input())
SWITCH = False

for i in range(Q):
    v = list(input().split())
    if v[0] == '1':
        if SWITCH:
            SWITCH = False
        else:
            SWITCH = True

    else:
        if v[1] == '1':
            if SWITCH==False:
                S = v[2] + S
            else:
                S = S + v[2]
        else:
            if SWITCH==False:
                S = S + v[2]
            else:
                S = v[2] + S

if SWITCH:
    print(S[::-1])
else:
    print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
SWITCH = False

for i in range(Q):
    v = list(input().split())
    if v[0] == '1':
        SWITCH = not SWITCH

    else:
        if v[1] == '1':
            if SWITCH==False:
                S.appendleft(v[2])
            else:
                S.append(v[2])
        else:
            if SWITCH==False:
                S.append(v[2])
            else:
                S.appendleft(v[2])

S = ''.join(S)

if SWITCH:
    print(S[::-1])
else:
    print(S)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
total = 1
for i in a:
  total = total * i
  
if total > 10**18:
    print("-1")
else:
  print(total)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
if 0 in l:
  print(0)
  exit()
ans = 1
for i in range(n):
  ans *= l[i]
  if ans > 10**18:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    """
    stack = deque()
    for i in range(H):
        tmp = list(input())
        for j in range(W):
            A[i][j] = tmp[j]
            if tmp[j] == "#":
                stack.append((i,j))
    """
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        #print(ans, stack)
        flag = False
        new_stack = deque()
        #for a,b in stack:
        while stack:
            a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
            if a != 0: # 上
                if A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
            if a != H-1: # 下
                if A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            if b != 0: # 左
                if A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            if b != W-1: # 右
                if A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


if __name__ == "__main__":
    main()




### FIXED CODE ###

from collections import deque

def main():
    H,W = map(int, input().split())

    A = [[a for a in input()] for _ in range(H)]
    #stack = deque([(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"])
    stack = [(i, j) for i in range(H) for j in range(W) if A[i][j]=="#"]
    ans = 0
    flag = False
    if stack:
        flag = True
    while flag:
        ans += 1
        flag = False
        #new_stack = deque()
        new_stack = []
        for a,b in stack:
        #while stack:
            #a,b = stack.pop() # 取り出す
            # A[a][b]の隣接マスについて調べる
             # 上
            if a != 0 and A[a-1][b] == ".": # 白の場合
                    A[a-1][b] = "#"
                    new_stack.append((a-1,b))
             # 下
            if a != H-1 and A[a+1][b] == ".": # 白の場合
                    A[a+1][b] = "#"
                    new_stack.append((a+1,b))
            # 左
            if b != 0 and A[a][b-1] == ".": # 白の場合
                    A[a][b-1] = "#"
                    new_stack.append((a,b-1))
            # 右
            if b != W-1 and A[a][b+1] == ".": # 白の場合
                    A[a][b+1] = "#"
                    new_stack.append((a,b+1))
        stack = new_stack
        if stack:
            flag = True
        else:
            ans -= 1 

    print(ans)
            


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

primes = [0, 0] + [1] * 49999
for i in range(2, 225):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0

while True:
    n = int(input())
    if n == 0:
        break
    print(sum(primes[i] and primes[n-i] for i in range(2, n//2+1)))

### FIXED CODE ###

import bisect
primes = [0, 0] + [1] * 49999
for i in range(2, 224):
    if primes[i]:
        for j in range(i*i, 50001, i):
            primes[j] = 0
values = [i for i, k in enumerate(primes) if k]
while True:
    n = int(input())
    if n == 0:
        break
    I = bisect.bisect(values, n//2)
    print(len([1 for v in values[:I] if primes[n-v]]))
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
cnt = n * (n - 1) * (n - 2) / 6
jud = []

for i in range(n):
    for j in range(n):
        if i > j:
            jud.append(L[i] + L[j])

for p in range(len(jud)):
    for m in range(n):
        if L[m] >= jud[p]:
            cnt -= 1

if cnt < 0:
    print(0)
else:
    print(int(cnt))

### FIXED CODE ###

from _bisect import bisect_left
from _bisect import bisect_right

n = int(input())
L = list(map(int, input().split()))
L = sorted(L)

cnt = 0

for a in range(n):
    for b in range(n):
        if a < b:
            c = bisect_left(L, L[a] + L[b], b)
            cnt += c - b - 1
print(cnt)
### BUGGY CODE ###

from decimal import Decimal
n = int(input())
a = []
r = {}
for i in range(n):
    d = Decimal(input())
    d *= 10**9
    d2 = 0
    d5 = 0
    while True:
        if d % 2 != 0 and d % 5 != 0:
            break
        if d % 2 == 0:
            d //= 2
            d2 += 1
        if d % 5 == 0:
            d //= 5
            d5 += 1
    a.append((d2,d5))
    r[(d2,d5)] = r.get((d2,d5),0) + 1
ans = 0
for x , y in r.keys():
    for i , j in r.keys():
        if min(x+i,y+j) >= 18:
            ans += r[(x,y)]*r[(i,j)]
            if x == i and y == j:
                ans -= r[(x,y)]
                
print(ans//2)

### FIXED CODE ###

from decimal import Decimal
n = int(input())
a = []
r = {}
for i in range(n):
    d = int(float(input())*10**9 + 0.1)
    d2 = 0
    d5 = 0
    while True:
        if d % 2 != 0 and d % 5 != 0:
            break
        if d % 2 == 0:
            d //= 2
            d2 += 1
        if d % 5 == 0:
            d //= 5
            d5 += 1
    a.append((d2,d5))
    r[(d2,d5)] = r.get((d2,d5),0) + 1
ans = 0
for x , y in r.keys():
    for i , j in r.keys():
        if min(x+i,y+j) >= 18:
            ans += r[(x,y)]*r[(i,j)]
            if x == i and y == j:
                ans -= r[(x,y)]
                
print(ans//2)
### BUGGY CODE ###

import queue

def dijkstra(g,node_count,start_index):

    INF = 10**9+7
    node = [INF] * node_count
    conf = [0] * node_count
    root = [-1] * node_count

    q = queue.Queue()
    q.put(0)
    root[0] = 0
    while not q.empty():

        p = q.get()
        conf[p] = 1
        for i in range(node_count):
            if root[i] < 0 and g[p][i] > 0 and i != p:
                q.put(i)
                root[i] = p

    return root


n, m = map(int, input().split())
r = []
#g = np.zeros((n,n))
g = [[0] * n for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    g[a-1][b-1] = 1
    g[b-1][a-1] = 1
    #r.append([a,b])
#for i in range(n):
#    print(g[i])
#c = dijkstra_heapq(g,n,0)
#print(c)
c = dijkstra(g,n,0)

#c = np.array(c) + 1
#print(c)
ans = []
for i in range(1,n):
    if c[i] >= 0:
        ans.append(c[i]+1)
    else:
        print('No')
        exit()

print('Yes')
for i in range(len(ans)):
    print(ans[i])


### FIXED CODE ###

import queue
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

#print(g)

root = [0] * n
count = 0
q = queue.Queue()
q.put(0)
root[0] = 1
count += 1
while not q.empty():
    p = q.get()
    for i in g[p+1]:
        if root[i-1] <= 0:
            q.put(i-1)
            root[i-1] = p + 1
            count += 1
            #print(p,i,count,root)
            if count >= n:
                break


if count < n:
    print('No')
    exit()
else:
    print('Yes')
    for i in range(1,n):
        print(root[i])
### BUGGY CODE ###

n=int(input())
a=[]
m=[]
b=[]
for i in range(n):
  a.append(input())
for i in range(n):
  b.append(a.count(a[i]))
kaisu=max(b)
for i in range(n):
  if kaisu==b[i]:
    m.append(a[i])
m=sorted(list(set(m)))
n=len(m)
for i in range(n):
  print(m[i])

### FIXED CODE ###

n=int(input())
s=[input() for i in range(n)]
s=sorted(s)
poll=[s[0]]
counta=[1]
kind=0
for i in range(1,n):
  if s[i]==s[i-1]:
    counta[kind]+=1
  else:
    kind+=1
    poll.append(s[i])
    counta.append(1)
m=max(counta)
for i in range(kind+1):
  if counta[i]==m:
    print(poll[i])
### BUGGY CODE ###

#!/usr/bin/env python3
#dp5 #Knapsack 2
#個数制限ありナップサック
#1≤W≤10**9
import sys
def LI(): return list(map(int, sys.stdin.readline().split()))
def LIR(n): return [LI() for _ in range(n)]
def e():
    n,W = LI()
    wv = LIR(n)

    #横:価値　縦:品物
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            #i番目の品物の価値より価値の制限が小さいとき(i番目の品物が使えないとき)
            if j < wv[i-1][1]:
                #i-1番目の品物の重さと同じ
                dp[i][j] = dp[i-1][j]
            else:
                #i番目の品物を使い、重さを追加する場合と使わない場合の重さを比較
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    #重さWまでの価値最大値
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()


### FIXED CODE ###

#!/usr/bin/env python3
#dp5 #Knapsack 2
#個数制限ありナップサック
#1≤W≤10**9

def e():
    n,W = map(int,input().split())
    wv = [list(map(int,input().split())) for _ in range(n)]
    #横:価値　縦:品物
    dp = [[float("inf") for _ in range(10**5+1)] for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range(10**5+1):
            #i番目の品物の価値より価値の制限が小さいとき(i番目の品物が使えないとき)
            if j < wv[i-1][1]:
                #i-1番目の品物の重さと同じ
                dp[i][j] = dp[i-1][j]
            else:
                #i番目の品物を使い、重さを追加する場合と使わない場合の重さを比較
                dp[i][j] = min(dp[i-1][j],dp[i-1][j - wv[i-1][1]] + wv[i-1][0])
    ans = 0
    #重さWまでの価値最大値
    for i in range(10**5+1):
        if dp[n][i] <= W:
            ans = i
    print(ans)
if __name__ == '__main__':
    e()
### BUGGY CODE ###

N = int(input())
X = [[] for _ in range(N)]
d = set()
ans = 0
for i in range(N):
    X[i] = list(map(int, input().split()))

for i in range(1, N):
    for j in range(i):
        d.add(abs(X[i][0]-X[j][0])+abs(X[i][1]-X[j][1]))
print(max(d))

### FIXED CODE ###

N = int(input())
X = [[] for _ in range(N)]
z = [0 for _ in range(N)]
w = [0 for _ in range(N)]
for i in range(N):
    X[i] = list(map(int, input().split()))
    z[i] = X[i][0] +X[i][1]
    w[i] = X[i][0] -X[i][1]

ans = max(max(z)-min(z), max(w)-min(w))
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
  ans = ans * i
  
if ans >= (10**9+7):
  ans  =  ans%(10**9+7)
  
print(ans)


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
  ans =  i* ans%(10**9+7) 

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

class Tree:
    def __init__(self):
        self.children = {}
        self.end = False

    def __contains__(self, key):
        if len(key) == 0:
            return self.end

        k, *rest = key
        if k not in self.children:
            return False

        return rest in self.children[k]

    def add(self, key):
        if len(key) > 0:
            k, *rest = key
            if k not in self.children:
                self.children[k] = self.__class__()

            self.children[k].add(rest)
        else:
            self.end = True


class Dictionary:
    def __init__(self):
        self.tree = Tree()

    def insert(self, word):
        self.tree.add(word)

    def find(self, word):
        return word in self.tree


def run():
    count = int(input())
    words = Dictionary()

    for _ in range(count):
        command, v = input().split()

        if command == 'insert':
            words.insert(v)
        elif command == 'find':
            if words.find(v):
                print('yes')
            else:
                print('no')
        else:
            raise ValueError()


if __name__ == '__main__':
    run()



### FIXED CODE ###

import sys 


class Tree:
    def __init__(self):
        self.children = {}
        self.end = False

    def __contains__(self, key):
        if len(key) == 0:
            return self.end

        k, *rest = key 
        if k not in self.children:
            return False

        return rest in self.children[k]

    def add(self, key):
        if len(key) > 0:
            k, *rest = key 
            if k not in self.children:
                self.children[k] = self.__class__()

            self.children[k].add(rest)
        else:
            self.end = True


class Dictionary:
    def __init__(self):
        self.tree = Tree()

    def insert(self, word):
        self.tree.add(word)

    def find(self, word):
        return word in self.tree


def run():
    _ = int(input())  # flake8: noqa
    words = Dictionary()

    for command in sys.stdin:

        if command.startswith('insert'):
            words.insert(command[7:])
        elif command.startswith('find'):
            if words.find(command[5:]):
                print('yes')
            else:
                print('no')
        else:
            raise ValueError()


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

R, G, B, N = map(int, input().split())
cnt = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        if (N - R * i - G * j) / B >= 0 and ((N - R * i - G * j) / B) % 1 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        if (N - R * i - G * j) / B >= 0 and ((N - R * i - G * j) / B) % 1 == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import Counter


class Node:

    def __init__(self, i):
        self.index = i
        self.parent = self
        self.height = 1

    def root(self):
        if self.parent == self:
            return self.parent
        else:
            self.parent = self.parent.root()
            return self.parent

    def unite(self, other):
        if self.root().height > other.root().height:
            self.root().parent = other.root()
            self.root().height = other.root().height + 1
        else:
            other.root().parent = self.root()
            other.root().height = self.root().height + 1

    def is_unite(self, other):
        return self.root() == other.root()


def solve(N, K, L, PQs, RSs):
    road_cities = [Node(i) for i in range(N + 1)]
    train_cities = [Node(i) for i in range(N + 1)]

    for p, q in PQs:
        road_cities[p].unite(road_cities[q])
    for r, s in RSs:
        train_cities[r].unite(train_cities[s])

    counts = Counter([
        (road_cities[i].root().index, train_cities[i].root().index)
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities[i].root().index, train_cities[i].root().index)]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))


### FIXED CODE ###

from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

    def is_unite(self, i, j):
        return self.root(i) == self.root(j)


def solve(N, K, L, PQs, RSs):
    road_cities = UnionFind(N)
    train_cities = UnionFind(N)

    for p, q in PQs:
        road_cities.unite(p, q)
    for r, s in RSs:
        train_cities.unite(r, s)

    counts = Counter([
        (road_cities.root(i), train_cities.root(i))
        for i in range(1, N + 1)
    ])

    ans = [
        counts[(road_cities.root(i), train_cities.root(i))]
        for i in range(1, N + 1)
    ]

    return " ".join([str(c) for c in ans])


if __name__ == "__main__":
    N, K, L = map(int, input().split(" "))
    PQs = []
    RSs = []
    for _ in range(K):
        PQs.append(tuple(map(int, input().split(" "))))
    for _ in range(L):
        RSs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, L, PQs, RSs))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
H = list(map(int, input().split()))

def rec(i):
    if i == 1:
        return 0
    if i == 2:
        return abs(H[0]-H[1])

    return min(rec(i-1)+abs(H[i-1]-H[i-2]), rec(i-2)+abs(H[i-1]-H[i-3]))
print(rec(N))


### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
dp = [0] * N
for i in range(1, N):
    if i == 1:
        dp[i] = abs(h[1] - h[0])
    else:
        dp[i] = min(abs(h[i] - h[i-1])+dp[i-1], abs(h[i] - h[i-2])+dp[i-2])
print(dp[N-1])
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
MOD = 10 ** 9 + 7
dp = [1]
if 1 in a:
    dp.append(0)
else:
    dp.append(1)
for ith_stair in range(2, N + 1):
    if ith_stair in a:
        dp.append(0)
    else:
        dp.append((dp[ith_stair - 1] + dp[ith_stair - 2]) % MOD)
print(dp[N] % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
MOD = 10 ** 9 + 7
dp = [1]
if 1 in a:
    dp.append(0)
else:
    dp.append(1)
for ith_stair in range(2, N + 1):
    if ith_stair in a:
        dp.append(0)
    else:
        dp.append((dp[ith_stair - 1] + dp[ith_stair - 2]) % MOD)
print(dp[N] % MOD)
### BUGGY CODE ###

n = int(input())

power = 1
for i in range(n):
    power *= i+1

print(power%(1000000007))


### FIXED CODE ###

n = int(input())

power = 1
for i in range(n):
    power = power * (i+1)%1000000007
    power %= 1000000007

print(power)
### BUGGY CODE ###

from itertools import permutations
import numpy as np
N=int(input())
l=[i+1 for i in range(N)]
P=np.array(list(map(int, input().split())))
Q=np.array(list(map(int, input().split())))
counter=0
for t in permutations(l):
  tmp=np.array(t)
  if sum(P==tmp)==N:
    a=counter
    
  if sum(Q==tmp)==N:
    b=counter
    
  counter+=1
  
print(abs(a-b))

### FIXED CODE ###

from itertools import permutations

N=int(input())
l=[i+1 for i in range(N)]
P=tuple(map(int, input().split()))
Q=tuple(map(int, input().split()))
counter=0
for t in permutations(l):
  if P==t:
    a=counter
    
  if Q==t:
    b=counter
    
  counter+=1
  
print(abs(a-b))