Harryxun/stf_run huggingface dataset:
import numpy as np

# 入力
# 重さと価値はループのなかで都度取得する
N, W = map(int, input().strip().split())

# 初期化
dp = np.zeros(W + 1, dtype='int64')

# dpテーブル
for i in range(N):
    w, v = map(int, input().strip().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(dp[-1])

### FIXED CODE ###

# dp[v] i番目までの品物で、価値がv以上になるよう選んだときの重さの最小値。
# 品物を増やすごとに、配列を更新して使いまわす。
# とれる価値の最大値VmaxはN*max(vi) 添え字は0<=v<=Vmax dpリストの長さはVmax+1
# ループは1~N回回す　添え字は0<=i<=N-1<N
# 解答はN回ループした後のdp[j]<=Wとなる最大のj

import numpy as np

# 入力 table[i][0]は重さ、table[i][1]は価値
N, W = map(int, input().strip().split())
t = []
for i in range(N):
    t.append(list(map(int, input().strip().split())))
table = np.array(t)

# 初期化 wiの最大値は10^9
Vmax = N * max(table[:, 1])
dp = np.full(Vmax + 1, 10 ** 9)
dp[0] = 0

# dp
for i in range(N):
    w = table[i][0]
    v = table[i][1]
    dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

# 解答　dpの後ろから見て、最初にWを下回ったときのi
for j in range(Vmax, 0, -1):
    if dp[j] <= W:
        print(j)
        break
while 1:
    numbers = map(int, raw_input())
    dp = [[0] * 10 for _ in xrange(10)]
    dp[0] = numbers
    for i in xrange(9):
        for j in xrange(len(dp[i]) - 1):
            dp[i + 1][j] = (dp[i][j] + dp[i][j + 1]) % 10
    print dp[-1][0]

### FIXED CODE ###

while 1:
    try:
        numbers = map(int, raw_input())
    except EOFError:
        break
    dp = [[0] * 10 for _ in xrange(10)]
    dp[0] = numbers
    for i in xrange(9):
        for j in xrange(len(dp[i]) - 1):
            dp[i + 1][j] = (dp[i][j] + dp[i][j + 1]) % 10
    print dp[-1][0]
a ,b = map(int ,raw_input().split())
if a%2=0 or b%2=0:
  print Even
else:
  print Odd


### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")
s = input()
a = s.sort()
if s != s.sort():
  print('No')
  exit()
  
if s[0:len(s)//2] == a[0:len(s)//2]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()

def kaibun(s):
    if s == s[::-1]:
        return 1
    else:
        return 0
        
q = len(s)
d = int((q-1)/2)
ket = s[0:d]
mat = s[int((q+1)/2):q]

if (kaibun(s) + kaibun(ket) + kaibun(mat)) == 3:
    print('Yes')
else:
    print('No')
N = int(input())
A = []
A = input().split()
ans = 1

for x in range(N):
    for y in range(N):
        if(x == y):
            continue
        if(A[x] == A[y]):
            ans = 0
            break

if(ans == 1):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S, T = map(str,input().split())
A, B = map(int,input().split())
U = str(input())

if(S == U):
    A -= 1
elif(T == U):
    B -= 1
else:
    A
    B
    
print("{} {}".format(A, B))
n = int(input())
lr = [int(i) for i in input().split()]

ans = 0

for i in range(n):
  ans += lr[i][1] -lr[i][0] +1
  
  
print(ans)

### FIXED CODE ###

n = int(input())
lr = [[int(i) for i in input().split()] for _ in range(n)]

ans = 0

for i in range(n):
  ans += (lr[i][1] - lr[i][0]) +1
  
  
print(ans)
#1,2,3の番号がついた3マスに，それぞれ"0"か"1"がある．"1"のマスはいくつあるか

s1,s2,s3 = a = map(int,input().split())

res = (s1+s2+s3)
print (res)


### FIXED CODE ###

#1,2,3の番号がついた3マスに，それぞれ"0"か"1"がある．"1"のマスはいくつあるか

s = input()
a = [int(c) for c in s]
print (a[0]+a[1]+a[2])
def main():
    x,y = map(int,input().split())
    tmp = []
    for i in range(2,max(2,min(int(x // 2)+1, int(y //2 )+1))):
        if x % i ==0 and y % i == 0:
            tmp.append(i)
            while True:
                if x % i == 0:
                    x = x//i
                else:
                    break
            while True:
                if y % i == 0:
                    y = y//i
                else:
                    break


    print(len(tmp) + 1)
    # print(tmp)
    # for i,a in enumerate(tmp):
    #     if a < 4:
    #         tmp[i] = 1
    #         continue
    #     j = 2
    #     for j in range(2,int(a**0.5)+1):
    #         if a % j == 0:
    #             tmp[i] = 0
    #             break
    #     if tmp[i] != 0:
    #         tmp[i] = 1
    # print(sum(tmp))
    # print(tmp)

    # cnt = 0
    # # print(tmp)
    # flg = 0
    # for i,a in enumerate(tmp):
    #     # print('out' + str(i) + ' ' + str(a))
    #     if a == 1:
    #         continue
    #     leng = len(tmp)
    #     for j in range(i+1,leng):
    #         # print(j)
    #         # print(tmp)
    #         # print(leng)
    #         if flg == 1:
    #             j -=1
    #         flg = 0
    #         if j >= leng:
    #             break
    #         # print(str(j) + ' ' + str(leng) + ' ' + str(tmp[j]))
    #         if tmp[j] % a == 0:
    #             tmp.pop(j)
    #             leng -=1
    #             j -= 1
    #             # print(tmp)
    #             # print(j)
    #             flg = 1
    #
    #                 # print(j)
    #                 # print(a)
    #

    # print(len(tmp))
    # print(tmp)
if __name__=='__main__':
    main()


### FIXED CODE ###

n=int(input())
i=1
count = 0
while i <= n:
    if i % 2 == 1:
        count+=1
    i+=1

print(count/n)
n,m=map(int,input().split())
a=[int(input())for _ in range(m)]
mod=10**9+7

dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if a[0]!=1 else 0

for i in range(2,n+1):
	if i in a:
		continue
	dp[i] = dp[i-2]+dp[i-1]
	dp[i]%=mod
print(dp[n])


### FIXED CODE ###

n,m=map(int,input().split())
dic =[0]*1234567
for _ in range(m):
	dic[int(input())]+=1

mod=10**9+7
if n==1:
	print(1)
	exit()
dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if dic[1]!=1 else 0

for i in range(2,n+1):
	if dic[i]:
		continue
	dp[i] = dp[i-2]+dp[i-1]
	dp[i]%=mod
print(dp[n])
import sys


def g(a,b):
    return g(abs(a-b),a) if a%abs(a-b)!=0 else abs(a-b)

for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    c = g(a, b)
    print(c, a*b//c)

### FIXED CODE ###

import sys
 
def gcd(inta, intb):
    large = max(inta, intb)
    small = min(inta,intb)
    mod = large % small
    if mod ==0:
        return small
    else:
        return gcd(small, mod) 
     
def lcm(inta, intb, intgcd):
    return (inta * intb // intgcd)
 
sets = sys.stdin.readlines()
for line in sets:
    a, b = map(int, line.split())
    c = gcd(a, b)
    print(c, lcm(a, b, c))
N = int(input())
t=0
x=0
y=0
for i in range(N)
    nt, nx, ny = map(int, input().split())
    km = abs(nx-x) + abs(ny-y)
    if km > (nt-t) or (km - (nt-t)) % 2 = 1:
        print("No")
        exit(0)
    t, x, y = nt, nx, ny
print("Yes")


### FIXED CODE ###

t, x, y = 0, 0, 0
for i in range(int(input())):
    next_t, next_x, next_y = map(int, input().split())
    diff = abs(x - next_x) + abs(y - next_y)
    if diff > (next_t - t) or (diff - (next_t - t)) % 2 == 1:
        print("No")
        exit(0)
    t, x, y, = next_t, next_x, next_y
print("Yes")
n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
visited0 = [0]*n
def dfs0(v, parent = -1):
    if dist0[v] == INF:
        dist0[v] = dist0[parent]+1
    for next_v in es[v]:
        if dist0[next_v] == INF:
            dfs0(next_v,v)
dfs0(0)

distn = [INF] * n
distn[n-1] = 0
visitedn = [0]*n
def dfsn(v, parent = -1):
    if distn[v] == INF:
        distn[v] = distn[parent]+1
    for next_v in es[v]:
        if distn[next_v] == INF:
            dfsn(next_v,v)
dfsn(n-1)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')


### FIXED CODE ###

n = int(input())

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')
a=int(input())
s=input()
if a>=3200:
    print(s)
else:
    print(red)

### FIXED CODE ###

a=int(input())
s=input()
if a>=3200:
    print(s)
else:
    print("red")
import numpy as np
N, C = map(int, input().split())
X = {}
V = {}
for i in range(1, N+1):
    X[i], V[i] = map(int, input().split())
    
x = np.zeros([N, 6])
for i in range(N):
    x[i, 0] = X[i+1]
    x[i, 1] = V[i+1]
    
    x[i, 2] = min(x[i, 0], abs(C-x[i, 0]))
x[:, 4] = x[:, 1] - x[:, 2]
x[x[:, 0] == x[:, 2], 3] = 1
tmp = 0


result = 0
while max(x[x[:, 5]==0, 4]) > 0:
    max_arg_i = np.argmax(x[:, 4])
    now_best = x[max_arg_i]
    get_flag = np.logical_and(np.logical_and(x[:, 2] <= now_best[2], x[:, 3] == now_best[3]), x[:, 5] == 0)
    temp_get_cal = sum(x[get_flag, 1]) - now_best[2]
    x[get_flag, 5] = 1
    result += temp_get_cal
    x[:, 0] = abs(x[:, 0] - now_best[0])
    x[get_flag, 1] = 0
    for i in range(N):
        x[i, 2] = min(x[i, 0], abs(C-x[i, 0]))
    x[:, 4] = x[:, 1] - x[:, 2]
    x[x[:, 0] == x[:, 2], 3] = 1
print(int(result))

### FIXED CODE ###

N, C = map(int, input().split())
X = {}
V = {}
for i in range(N):
    X[i], V[i] = map(int, input().split())

left, right = [], []
left.append(V[0] - X[0])
right.append(V[N-1] - (C - X[N-1]))
for i in range(1, N):
    left.append(left[i-1] + V[i] - X[i] + X[i-1])
    right.append(right[i-1] + V[N-i-1] - (C - X[N-i-1]) + (C - X[N-i]))

left_max = [0]
for i in range(N):
    if left[i] > left_max[i]:
        left_max.append(left[i])
    else:
        left_max.append(left_max[i])
right_max = [0]
for i in range(N):
    if right[i] > right_max[i]:
        right_max.append(right[i])
    else:
        right_max.append(right_max[i])
result = set()
for i in range(N):
    result.add(left[i]-X[i]+right_max[N-1-i])
for i in range(N):
    result.add(right[i]-(C - X[N-i-1])+left_max[N-1-i])
result = max(max(left_max), max(right_max), max(result))
print(result)
import numpy as np
N,M = map(int,input().split())

x = []
y = []
z = []
for k in range(N):
    xx,yy,zz = map(int,input().split())
    x.append(xx)
    y.append(yy)
    z.append(zz)

ite = [-1,1]

s_ori = np.stack([x,y,z])
cc = []
for i in ite:
    for j in ite:
        for k in ite:
            s = s_ori.copy()
            s[0,:] *= i
            s[1,:] *= j
            s[2,:] *= k
            a = np.sum(s,axis = 0)
            b = np.sort(a)[::-1][:M]
            c = sum(b)
            cc.append(c)
print(np.max(cc))

### FIXED CODE ###

import numpy as np
N,M = map(int,input().split())

x = []
y = []
z = []
for k in range(N):
    xx,yy,zz = map(int,input().split())
    x.append(xx)
    y.append(yy)
    z.append(zz)

ite = [-1,1]

s_ori = np.vstack([x,y,z])
cc = []
for i in ite:
    for j in ite:
        for k in ite:
            s = s_ori.copy()
            s[0,:] *= i
            s[1,:] *= j
            s[2,:] *= k
            a = np.sum(s,axis = 0)
            b = np.sort(a)[::-1][:M]
            c = sum(b)
            cc.append(c)
print(np.max(cc))
N,M,K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

S = [0]

Sum = 0


for i in range(N):
  K = K - A[i]
  if K > 0:
    Sum += 1
  else:
    K = K + A[i]
    break
S.append(Sum)

for j in range(M):
  K = K - B[j]
  if K > 0:
    Sum += 1
  else:
    if Sum == 0:
      break
    while(K<0):
      i = i - 1
      K = K + A[i]
      Sum = Sum - 1
    Sum += 1
  S.append(Sum)
print(max(S))

### FIXED CODE ###

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

S = [0]

Sum = 0


for i in range(N):
  K = K - A[i]
  if K >= 0:
    Sum += 1
  else:
    K = K + A[i]
    break
else:
  i = N
S.append(Sum)

for j in range(M):
  K = K - B[j]
  if K >= 0:
    Sum += 1
  else:
    if i == 0:
      break
    for k in range(i):
      K = K + A[i-k-1]
      
      Sum = Sum - 1
      if K >= 0:
        i = i-k-1
        break
    else:
      i = 0
      continue
    if K >= 0:
      Sum += 1
    
  S.append(Sum)
 
print(max(S))
a = int(input())
for i in range(a):
    x1,y1,x2,y2,x3,y3,x4,y4=list((map(float,raw_input().split())))
    if ((x2-x1)*(y4-y3)-(y2-y1)*(x4-x3)) < 1e-10:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

n = int(input())
for i in range(n):
    x1,y1,x2,y2,x3,y3,x4,y4=map(float,input().split())
    print("YES" if abs((y2-y1)*(x4-x3)-(x2-x1)*(y4-y3)) < 1e-10 else "NO")
impport sys

n = int(input())

for i in range(n):
  t,x,y = map(int,input().split())
  if (x + y) > t or (x + y + t) % 2:
    print("No")
    sys.exit()
  print("Yes")

### FIXED CODE ###

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


A = a*b % 2

if A==0:
    print("Even")

else:
    print("Odd")
A = input()
B = input()
C = input()

now = A [0]
a = 1
b = 0
c = 0
while True:
    if now == 'a':
        if a + 1 == len(A):
            res = 'A'
            break
        now = A[a+1]
        a = a + 1
        
    if now == 'b':
        if b + 1 == len(B):
            res = 'B'
            break
        now = B[b+1]
        b = b + 1
        
    if now == 'c':
        if c + 1 == len(C):
            res = 'C'
            break
        now = C[c+1]
        c = c + 1

print(res)

### FIXED CODE ###

A = input()
B = input()
C = input()

now = 'a'
a = 0
b = 0
c = 0

while True:
    if now == 'a':
        if a  == len(A):
            res = 'A'
            break
        now = A[a]
        a = a + 1
        
    elif now == 'b':
        if b  == len(B):
            res = 'B'
            break
        now = B[b]
        b = b + 1
        
    elif now == 'c':
        if c  == len(C):
            res = 'C'
            break
        now = C[c]
        c = c + 1

print(res)
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
    del set_index
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")
        


### FIXED CODE ###

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

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")
n = input()
if n == n[::-1]:
	print('Yes')
else:
	print('No')

### FIXED CODE ###

n = input()
if n[0] == n[2]:
	print('Yes')
else:
	print('No')
ope = {"+": lambda a, b: b + a,
	   "-": lambda a, b: b - a,
	   "*": lambda a, b: b * abs}
stack = []

for c in input().split():
	if c in ope:
		stack.append(ope[c](stack.pop(), stack.pop()))
	else:
		stack.append(int(c))

print(stack[-1])

### FIXED CODE ###

def push(x):
	global stack

	stack.append(x)

def pop():
	global stack

	ret = stack.pop()
	return ret

ope = {"+": lambda a, b: b + a,
	   "-": lambda a, b: b - a,
	   "*": lambda a, b: b * a}

if __name__ == '__main__':
	stack = []

	for c in input().split():
		if c in ope:
			push(ope[c](pop(), pop()))
		else:
			push(int(c))

	print(" ".join(map(str, stack)))
lines = list(map(int, input().split())
lines.sort()
             
print(lines[0] * lines[1])

### FIXED CODE ###

lines = list(map(int, input().split()))
lines.sort()
 
print((lines[0] * lines[1]) // 2)
import math
n = int(input())
s = int(input())
for i in range(1,n):
    t = int(input())
    s = (s*t)//math.gcd(s,t)

print(s)

### FIXED CODE ###

n = int(input())
s = int(input())
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)
for i in range(1,n):
    t = int(input())
    s = (s*t)//gcd_core(s,t)

print(s)
from collections import deque
import heapq
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
min_nk = min(n, k)
for l in range(k+1):
    if k-l > 0:
        for r in range(k-l+1):
            hand = []
            for i in range(1, l+1):
                hand.append(v[i-1])
            for i in range(1, r+1):
                hand.append(v[n-i])
            hand.sort()
            if k-l-r > 0:
                for back in range(k-l-r):
                    if len(hand) != 0:
                        if min(hand) < 0:
                            x = hand.index(min(hand))
                            hand[x] = 0
                ans = max(ans, sum(hand))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
min_nk = min(n, k)
for l in range(min_nk+1):
    for r in range(min_nk-l+1):
        hand = []
        for i in range(l):
            hand.append(v[i])
        for i in range(r):
            hand.append(v[n-1-i])
        hand.sort()
        
        for i in range(min(k-l-r, len(hand))):
            if hand[i] < 0:
                hand[i] = 0
        ans = max(ans, sum(hand))
print(ans)
N = int(input())
s = [input() for i in range(N)]

for i, s_i in enumerate(s):
    s_l = list(s_i)
    s_l.sort()
    a = ""
    for c in s_l:
        a += c
    s[i] = a

cnt = 0
count_dict = {}
for j in range(N):
    count_dict[s[j]] = 0
for k in range(N):
    count_dict[s[k]] += 1

for v in count_dict.values():
    cnt += factorial(v) / factorial(2) / factorial(v - 2)

print(cnt)

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


N = int(input())
s = [input() for i in range(N)]

for i, s_i in enumerate(s):
    s_l = list(s_i)
    s_l.sort()
    a = ""
    for c in s_l:
        a += c
    s[i] = a

cnt = 0
count_dict = {}
for j in range(N):
    count_dict[s[j]] = 0
for k in range(N):
    count_dict[s[k]] += 1

for v in count_dict.values():
    if v >= 2:
        # cnt += int(factorial(v)) / int(factorial(2)) / int(factorial(v - 2))
        cnt += cmb(v, 2)

print(cnt)
import sys

args = sys.argv[1]
args = int(args)
print(args*args)

### FIXED CODE ###

from sys import stdin

a = stdin.readline().rstrip()
a = int(a)
print(a*a)
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
a = b = A[0]
n = 0
c = 0
ans = [0,1]
for i in range(1,N+1):
    if  i == a:
        c = 0
        n += 1
        b = a
        if n <= M-1:
            a = A[n]
    elif i-2 == b:
        c = ans[-1]
    elif i-1 == b :
        c = ans[-2]
    else:
        c  = ans[-1] + ans[-2]
    c %= 10**9 + 7
    ans.append(c)
print(ans[-1])

### FIXED CODE ###

N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
n = 0
if M != 0:
    a = b = A[0]
else:
    a = b = -2
c = 0
ans = [0,1]
for i in range(1,N+1):
    if  i == a:
        c = 0
        n += 1
        b = a
        if n <= M-1:
            a = A[n]
    elif i-2 == b:
        c = ans[-1]
    elif i-1 == b :
        c = ans[-2]
    else:
        c  = ans[-1] + ans[-2]
    c %= 10**9 + 7
    ans.append(c)
print(ans[-1])
import sys
from collections import Counter as cc
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    sys.setrecursionlimit(10**4)
    n = ii()
    a = li()
    c = cc(a)
    N = sum(c.values())
    
    @lru_cache
    def dfs(x, y, z):
        if x== 0 and y == 0 and z == 0:
            return 0
        tmp = 1
        if x > 0:
            tmp += dfs(x-1, y, z)*x/N
        if y> 0:
            tmp += dfs(x+1, y-1, z)*y/N
        if z > 0:
            tmp += dfs(x, y+1, z-1)*z/N
        tmp *= N/(x+y+z)
        return tmp
    
    print(dfs(c[1], c[2], c[3]))

    

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import Counter as cc
from numba import njit
import numpy as np

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

# sys.setrecursionlimit(10**4)
n = ii()
a = li()
c = cc(a)
N = sum(c.values())
cache = np.full((N+1, N+1, N+1), -1, dtype=float)
cache[0][0][0] = 0
@njit(cache=True)
def dfs(x, y, z, N, cache):
    if x+y+z==0:
        return 0
    if cache[x][y][z]>=0:
        return cache[x][y][z]
    tmp = 1
    if x > 0:
        tmp += dfs(x-1, y, z,N, cache)*x/N
    if y > 0:
        tmp += dfs(x+1, y-1, z, N, cache)*y/N
    if z > 0:
        tmp += dfs(x, y+1, z-1, N, cache)*z/N
    tmp *= N/(x+y+z)
    cache[x][y][z] = tmp
    return tmp

dfs(c[1], c[2], c[3], N, cache)
print(cache[c[1]][c[2]][c[3]])
a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	print(f)
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)