Harryxun/stf_run huggingface dataset:
n = int(input())
x = input()
ans = [0]*(10**5+1)

for i in range(1,10**5+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

one_cnt = x.count('1')
numx = int(x,2)
for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx + 2**(n-1-i)
    else:
        temp -= 1
        num = numx - 2**(n-1-i)
    print(ans[num%temp]+1)


### FIXED CODE ###

n = int(input())
x = input()
ans = [0]*(n+1)

for i in range(1,n+1):
    s = format(i, 'b')
    c = s.count('1')
    a = i%c
    ans[i] += 1
    ans[i] += ans[a] 

one_cnt = x.count('1')
numx = int(x,2)

for i in range(n):
    temp = one_cnt
    if x[i]=='0':
        temp += 1
        num = numx%temp + pow(2,n-1-i,temp)
    else:
        if temp>1:
            temp -= 1
            num = numx%temp - pow(2,n-1-i,temp)
        else:
            print(0)
            continue
    print(ans[num%temp]+1)
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap
    return d


@lru_cache(maxsize=None)
def f(c1, c2, c3):
        if min(c1, c2, c3) < 0:
            return 0
        if c1 == c2 == c3 == 0:
            return 0

        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        ret += f(c1-1, c2, c3) * p1 / ip0
        ret += f(c1+1, c2-1, c3) * p2 / ip0
        ret += f(c1, c2+1, c3-1) * p3 / ip0
        return ret

@mt
def slv(N, A):
    ca = Counter(A)
    return f(ca[1], ca[2], ca[3])



def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
n,m=map(int,input().split())
List=[list(map(int,input().sprit())) for i in range(m)]
P=list(map(int,input().split()))

k=0
ans=0
flug=True

for i in range(n):
    k=bin(i)
    for l in range(m):
        count=0
        for j in range(List[l][0]):
            if ((k>>List[l][j+1])&1)==1:
                count += 1
        if count%2 != P[l]:
            flug=False
    if flug==True:
        ans += 1
        
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
List=[list(map(int,input().split())) for i in range(m)]
P=list(map(int,input().split()))

ans=0

for i in range(2**n):
    flug=True
    for l in range(m):
        count=0
        for j in range(List[l][0]):
            if ((i >> (List[l][j+1]-1))&1)==1:
                count += 1
        if count%2 != P[l]:
            flug=False
    if flug==True:
        ans += 1
        
print(ans)
S = list(input())
tmp = ''
L = len(S)
S.append('0')
S.append('0')
ans = 0
for i in range(L):
    tmp += str(S[i])
    if tmp=='dream':
        if tmp+str(S[i+1])+str(S[i+2])+str(S[i+3])=='dreamera':
            ans += len(tmp)
            tmp = ''
        elif tmp+str(S[i+1])+str(S[i+2])=='dreamer':
            ans += len(tmp)+2
            tmp = ''
            i+=2
        else:
            ans += len(tmp)
            tmp = ''
    if tmp == 'erase':
        if tmp+str(S[i+1])=='eraser':
            ans += len(tmp)+1
            tmp  = ''
            i+=1
        else:
            ans += len(tmp)
            tmp = ''
if ans == L:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

S = list(input())
tmp = ''
L = len(S)
S = S[-1:-L-1:-1]
Kouho = ['maerd','remaerd','esare','resare']
ans = 0
for i in range(L):
    
    tmp += str(S[i])
    if tmp in Kouho:
        ans += len(tmp)
        tmp = ''
if ans == L:
    print('YES')
else:
    print('NO')
import sys
#input = sys.stdin.readline
from collections import deque

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

initial = 0
grid = []
for _ in range(H):
    row = input()
    initial += row.count("#")
    grid.append(row)

def bfs():
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    q = deque()
    q.append((0, 0, 1))
    explored = set()
    explored.add((0, 0))
    while q:
        y, x, count = q.popleft()
        for h, w in dire:
            yh = y + h
            xw = x + w
            if yh < 0 or yh >= H or xw < 0 or xw >= W or grid[yh][xw] == "#" or (yh, xw) in explored:
                continue
            
            if (yh, xw) == (H-1, W-1):
                return count+1

            explored.add((yh, xw))
            q.append((yh, xw, count+1))

path_count = bfs()

print(H*W - path_count - initial)

            
            

### FIXED CODE ###

import sys
#input = sys.stdin.readline
from collections import deque

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

initial = 0
grid = []
for _ in range(H):
    row = input()
    initial += row.count("#")
    grid.append(row)

def bfs():
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    q = deque()
    q.append((0, 0, 1))
    explored = set()
    explored.add((0, 0))
    while q:
        y, x, count = q.popleft()
        for h, w in dire:
            yh = y + h
            xw = x + w
            if yh < 0 or yh >= H or xw < 0 or xw >= W or grid[yh][xw] == "#" or (yh, xw) in explored:
                continue
            
            if (yh, xw) == (H-1, W-1):
                return count+1

            explored.add((yh, xw))
            q.append((yh, xw, count+1))

    return -1

path_count = bfs()

if path_count == -1:
    print(-1)
else:
    print(H*W - path_count - initial)
def main():
    H, W, M = map(int, input().split())
    bombs = [list(map(int, input().split())) for i in range(M)]
    
    hw = [[0] * W for i in range(H)]
    
    for i in range(len(bombs)):
        [h, w] = bombs[i]
        hw[h - 1][w - 1] = 1
    
    wh = [list(x) for x in zip(*hw)]
    hw_tuple_list = []
    for i in range(len(hw)):
        hw_tuple_list.append((sum(hw[i]), i+1))
    
    wh_tuple_list = []
    for i in range(len(wh)):
        wh_tuple_list.append((sum(wh[i]), i+1))

    h_list = sorted(hw_tuple_list, reverse = True)
    w_list = sorted(wh_tuple_list, reverse = True)

    h_max = h_list[0][0]
    h_idx_list = []
    for i in range(len(h_list)):
        if h_max > h_list[i][0]:
            break
        h_idx_list.append(h_list[i][1])

    w_max = w_list[0][0]
    w_idx_list = []
    for i in range(len(w_list)):
        if w_max > w_list[i][0]:
            break
        w_idx_list.append(w_list[i][1])
    
    cnt = 1
    for i in range(len(h_idx_list)):
        for j in range(len(w_idx_list)):
            if hw[h_idx_list[i] - 1][w_idx_list[j] - 1] != 1:
                cnt = 0
                break
    return w_max + h_max - cnt

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

### FIXED CODE ###

def main():
    H, W, M = map(int, input().split())
    bombs = [list(map(int, input().split())) for i in range(M)]
    
    if M == 1:
        return 1
    
    hw = [0] * H
    wh = [0] * W
    
    for i in range(len(bombs)):
        [h, w] = bombs[i]
        hw[h-1] += 1
        wh[w-1] += 1
    
    hw_tuple_list = []
    for i in range(len(hw)):
        hw_tuple_list.append((hw[i], i+1))
    
    wh_tuple_list = []
    for i in range(len(wh)):
        wh_tuple_list.append((wh[i], i+1))

    h_list = sorted(hw_tuple_list, reverse = True)
    w_list = sorted(wh_tuple_list, reverse = True)

    h_max = h_list[0][0]
    h_idx_list = []
    check_h = [0] * H
    for i in range(len(h_list)):
        if h_max > h_list[i][0]:
            break
        h_idx_list.append(h_list[i][1])
        check_h[h_list[i][1]-1] = 1

    w_max = w_list[0][0]
    w_idx_list = []
    check_w = [0] * W
    for i in range(len(w_list)):
        if w_max > w_list[i][0]:
            break
        w_idx_list.append(w_list[i][1])
        check_w[w_list[i][1]-1] = 1
    
    cnt = 0
    for [h, w] in bombs:
        if check_h[h-1] == 1 and check_w[w-1] == 1:
            cnt += 1
    return h_max + w_max if cnt != len(h_idx_list) * len(w_idx_list) else h_max + w_max - 1

if __name__ == '__main__':
    print(main())
# -*- coding: utf-8 -*-
import sys
lines = sys.stdin.readlines()
l = 0
while lines[l]!="-":
 s = lines[l].replace('\n','')
 n = lines[l+1]
 l += 2
 t = sum([lines[i] for i in xrange(l, l+n)]) % len(s)
 print s[t:]+s[:t]
 l += n

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
lines = sys.stdin.readlines()
l = 0
while not ("-" in lines[l]):
 s = lines[l].replace('\n','')
 n = int(lines[l+1])
 l += 2
 t = sum(map(int, lines[l:l+n])) % len(s)
 print s[t:]+s[:t]
 l += n
import math

MOD = 1000000000 + 7

n = list(map(int,input().split()))
N = n[0]
K = n[1]

for i in range(1,K+1):
    blue = (math.factorial(K-1)/(math.factorial(K-i) * math.factorial(i-1))) % MOD
    red = (math.factorial(N-K+1)/(math.factorial(N-K-i+1) * math.factorial(i))) % MOD
    print((int)((red * blue) % MOD))

### FIXED CODE ###

n,k=map(int,input().split())
ans=0
MOD=(10**9)+7

fact_ans=[1 for _ in range(n+1)]
for i in range(1,n+1):
    fact_ans[i]=fact_ans[i-1]*i

def fact(n):
    if(n<0):
        return 1
    else:
        return fact_ans[n]

for i in range(1,k+1):
    blue=fact(k-1)//(fact(k-i)*fact(i-1))
    red=( fact(n-k+1)//( fact(i)*fact(n-k+1-i))  )
    print((blue*red)%MOD)
ch=input()

if ch[:n//2]==ch[n//2:]:
  print('Yes')
else:
   print('No')

### FIXED CODE ###

n=int(raw_input())
ch=raw_input()
if ch[:n//2]==ch[n//2:]:
        print('Yes')
else:
        print('No')
from sys import stdin
from sys import  setrecursionlimit
setrecursionlimit(3000)

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs=[]
for i in range(N):
    [A, B] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(A)
    Bs.append(B)

#dp_map = []
#for i in range(N+1):
#    temp_arr = [-1 for _ in range(H+1)]
#    dp_map.append(temp_arr)
dp_map = [[-1]*(H+1) for _ in range(N+1)]
#dp_map = [[-1]*(H+1)]*(N+1)
#print(len(dp_map))
#print(len(dp_map[0]))

def DP(i, j):
    if j<=0:
        return 0
    if dp_map[i][j]!=-1:
        return dp_map[i][j]
    
    if i==1:
        dp_map[i][j] = DP(i,j-As[i-1])+Bs[i-1]
        return dp_map[i][j]

    dp_map[i][j] = min(DP(i-1,j),DP(i,j-As[i-1])+Bs[i-1])
    return dp_map[i][j]

print(DP(N,H))

### FIXED CODE ###

from sys import stdin
from sys import  setrecursionlimit
setrecursionlimit(10000)

[H, N] = [int(x) for x in stdin.readline().rstrip().split()]
As = []
Bs=[]
for i in range(N):
    [A, B] = [int(x) for x in stdin.readline().rstrip().split()]
    As.append(A)
    Bs.append(B)

INF = 10**10
dp_map = [[INF]*(H+1) for _ in range(N+1)]

#dp_map[i][j]: i番目の魔法までを使って、最低でもjのダメージを与える時に必要なMP
dp_map[0][0]  = 0
for i in range(N):
    for j in range(H+1):
        if j<As[i]:
            dp_map[i+1][j] = min(dp_map[i+1][0]+Bs[i],dp_map[i][j])
        else:
            dp_map[i+1][j] = min(dp_map[i+1][j-As[i]]+Bs[i] ,dp_map[i][j])

print(dp_map[N][H])
s = input()
n = int(input())
query = []
for i in range(n):
    query.append(input().split())
cond = 1
deque(s)
for i in range(n):
    if query[i] == ['1']:
        cond *= -1
    else:
        if cond == 1:
            if query[i][1] == '1':
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])
        else:
            if query[i][1] == '2':
                s.appendleft(query[i][2])
            else:
                s.append(query[i][2])

result = ''.join(s)
if cond == -1:
    result = result[::-1]
print(result)


### FIXED CODE ###

from collections import deque
s = input()
n = int(input())
query = []
for i in range(n):
    query.append(input().split())
cond = 1
word = deque(s)
for i in range(n):
    if query[i] == ['1']:
        cond *= -1
    else:
        if cond == 1:
            if query[i][1] == '1':
                word.appendleft(query[i][2])
            else:
                word.append(query[i][2])
        else:
            if query[i][1] == '2':
                word.appendleft(query[i][2])
            else:
                word.append(query[i][2])

result = ''.join(word)
if cond == -1:
    result = result[::-1]
print(result)
# -*- coding: utf-8 -*-
# import math

memo

def conbination(n, r):
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    if r == 0:
        return 1
    bunshi = 1
    for i in range(n, n-r, -1):
        bunshi *= i
    bunbo = 1
    for i in range(r, 0, -1):
        bunbo *= i
    return bunshi // bunbo

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

for i in range(1, K+1):
    c_blue = conbination(K-1, i-1)
    c_red = conbination(N-K+1, i)
    print((c_blue * c_red) % (10**9 + 7))


### FIXED CODE ###

# -*- coding: utf-8 -*-

def conbination(n, r):
    return f[n] // (f[r] * f[n-r])

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

f = [1]
for i in range(1, N+1):
    f.append(int(f[i-1]*i))

for i in range(1, K+1):
    if i > N-K+1:
        print(0)
        continue
    c_blue = conbination(K-1, i-1)
    c_red = conbination(N-K+1, i)
    print((c_blue * c_red) % (10**9 + 7))
n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -10**18
for now in range(n):
	ruisekiwa = []
	tansaku = set()
	for i in range(n+1):
		targ = p[now]-1
		if len(ruisekiwa) >= 1:
			ruisekiwa.append(c[targ]+ruisekiwa[-1])
		else:
			ruisekiwa.append(c[targ])
		if targ in tansaku:
			break
		now = targ
		tansaku.add(targ)
	#print(ruisekiwa)
	if len(ruisekiwa) >= k:
		tr = max(ruisekiwa[:k])
		#print(tr)
		ans = max(ans, tr)
	else:
		if ruisekiwa[0] < ruisekiwa[-1]:
			#print(ruisekiwa[-1]-ruisekiwa[0])
			ms = (k//(len(ruisekiwa)-1))*(ruisekiwa[-1]-ruisekiwa[0])
			#print(ms)
			tr = max(max(ruisekiwa[:k%(len(ruisekiwa)-1)])+ms, max(ruisekiwa)+ms-(ruisekiwa[-1]-ruisekiwa[0]))
			#print(tr)
			ans = max(ans, tr)
		else:
			tr = max(ruisekiwa)
			ans = max(ans, tr)
print(ans)

### FIXED CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = -10**18
for now in range(n):
	ruisekiwa = []
	tansaku = set()
	for i in range(n+1):
		targ = p[now]-1
		if len(ruisekiwa) >= 1:
			ruisekiwa.append(c[targ]+ruisekiwa[-1])
		else:
			ruisekiwa.append(c[targ])
		if targ in tansaku:
			break
		now = targ
		tansaku.add(targ)
	#print(ruisekiwa)
	if len(ruisekiwa) >= k:
		tr = max(ruisekiwa[:k])
		#print(tr)
		ans = max(ans, tr)
	else:
		if ruisekiwa[0] < ruisekiwa[-1]:
			#print(ruisekiwa[-1]-ruisekiwa[0])
			ms = (k//(len(ruisekiwa)-1))*(ruisekiwa[-1]-ruisekiwa[0])
			#print(ms)
			#print(len(ruisekiwa))
			#print(ruisekiwa[:k%(len(ruisekiwa)-1)+1])
			if k%(len(ruisekiwa)-1) >= 1:
				tr = max(max(ruisekiwa[:k%(len(ruisekiwa)-1)])+ms, max(ruisekiwa)+ms-(ruisekiwa[-1]-ruisekiwa[0]))
			else:
				tr = max(ruisekiwa[:-1])+ms-(ruisekiwa[-1]-ruisekiwa[0])
			#print(tr)
			ans = max(ans, tr)
		else:
			tr = max(ruisekiwa)
			ans = max(ans, tr)
print(ans)
from math import pi, tan
EPS = 0.0000000001

def f(a, b, theta):
    if theta >= pi * 0.5:
        return 0.0
    elif tan(theta) >= b / a:
        return a * b**2 * 0.5 / tan(theta)
    else:
        return a**2 * b - a**2 *b * 0.5 * tan(theta)

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

l = 0
r = pi * 0.5
while r - l >= EPS:
    mid = (l + r) * 0.5
    if f(a, b, theta) >= x:
        l = mid
    else:
        r = mid

print("{:.10f}".format(l / pi * 180))


### FIXED CODE ###

from math import pi, sin, cos, tan
EPS = 0.0000000001

def f(a, b, theta):
    if theta > pi * 0.5 - EPS:
        ret = 0.0
    elif a * tan(theta) <= b:
        ret = a**2 * b - a**3 * tan(theta) * 0.5
    else:
        ret = a * b**2 * 0.5 / tan(theta)

    return ret

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

ok = pi * 0.5
ng = 0.0
while ok - ng >= EPS:
    mid = (ok + ng) * 0.5
    if f(a, b, mid) < x:
        ok = mid
    else:
        ng = mid
print("{:.10f}".format(ok / pi * 180))
lt=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
c=input()
for i in range(26):
  if c=lt[i]:
    break
print(lt[i+1])

### FIXED CODE ###

lt=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
c=input()
for i in range(26):
  if c==lt[i]:
    break
print(lt[i+1])
import math
MOD = 10**9 + 7
comb = lambda n, r: math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N, K = map(int, input().split(' '))
red = N - K
for i in range(K):
  res = comb(red + 1, i + 1) * comb(K - 1, i)
  res %= MOD
  print(res)

### FIXED CODE ###

import math
def comb(n, r):
  if n - r < 0:
    return 0
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
MOD = 10**9 + 7
N, K = map(int, input().split(' '))
red = N - K
for i in range(K):
  res = comb(red + 1, i + 1) * comb(K - 1, i)
  res %= MOD
  print(res)
def swap(a,b):
	x = a
	a = b
	b = x
	
'''
l = input().split()

l = list(map(int, l))
a,b,c = l[0],l[1],l[2]
'''
a,b,c = map(int, input().split)
if a > b:
	a,b = b,a

if b > c:
	b,c = c,b
	
if a > b:
	a,b = b,a
	
print(a,b,c)


### FIXED CODE ###


'''
l = input().split()

l = list(map(int, l))
a,b,c = l[0],l[1],l[2]
'''
a,b,c = map(int, input().split())
if a > b:
	a,b = b,a

if b > c:
	b,c = c,b
	
if a > b:
	a,b = b,a
	
print(a,b,c)
from bisect import bisect_left


while True:
	N, Q = map(int, input().split(' '))
	if N == 0:
		break

	era = {} # Like {1877: ('Meiji', 10)}

	years = [] # 西暦
	for _ in range(N):
		name, j, w = input().split(' ')
		j, w = int(j), int(w)
		era[w] = (name, j)
		years.append(w)
	years.sort()

	for _ in range(Q):
		q = int(input())
		y = years[bisect_left(years, q)]
		name, length = era[y]
		if q - y + length <= 0:
			print('Unknown')
		else:
			print(name + ' ' + str(q-y+length))



### FIXED CODE ###

from bisect import bisect_left


while True:
	N, Q = map(int, input().split(' '))
	if N == 0:
		break

	era = {} # Like {1877: ('Meiji', 10)}

	years = [] # 西暦
	for _ in range(N):
		name, j, w = input().split(' ')
		j, w = int(j), int(w)
		era[w] = (name, j)
		years.append(w)
	years.sort()

	for _ in range(Q):
		q = int(input())
		i = bisect_left(years, q)
		if i >= len(years):
			print('Unknown')
			continue
		y = years[i]
		name, length = era[y]
		if q - y + length <= 0:
			print('Unknown')
		else:
			print(name + ' ' + str(q-y+length))
antennas = [int(input()) for i in range(5)]

max_dist = int(input())

coords = {}

for i in range(len(antennas)):
  coords[i] = antennas[i]
flag = 1
for i in range():
  for j in range(i + 1, 5):
    if abs(coords[i] - coords[j]) > max_dist:
      print(':(')
      flag = 0
      break
  if flag = 0:
    break
if flag = 1:
  print('Yay!')
      
  

### FIXED CODE ###

antennas = [int(input()) for i in range(5)]

max_dist = int(input())

coords = {}

for i in range(len(antennas)):
  coords[i] = antennas[i]
flag = 1
for i in range(5):
  for j in range(i + 1, 5):
    if abs(coords[i] - coords[j]) > max_dist:
      print(':(')
      flag = 0
      break
  if flag == 0:
    break
if flag == 1:
  print('Yay!')
def fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
ans = fib(a[0])
for j in range(1,m):
    if m != 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
ans *= fib(n-a[m-1])
print(ans%1000000007)


### FIXED CODE ###

def fib(n):
    a, b = 1, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

n,m = map(int,input().split())
if m != 0:
  a = [int(input()) for i in range(m)]
  ans = fib(a[0])
  for j in range(1,m):
    if m == 1:
        continue
    elif a[j] == a[j-1]+1:
        ans = 0
    else:
        ans *= fib(a[j]-a[j-1]-1)
  ans *= fib(n-a[m-1])
else:
  ans = fib(n+1)
print(ans%1000000007)
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    fs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    bs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]

    g = [[] for _ in range(n)]
    for u, v in fs:
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)

    bg = [[] for _ in range(n)]
    for u, v in bs:
        bg[u - 1].append(v - 1)
        bg[v - 1].append(u - 1)

    ccmembs = []
    ccmap = [-1] * n
    def color_component(ccid, u):
        ccmap[u] = ccid
        nmemb = 1
        for v in g[u]:
            if ccmap[v] < 0:
                nmemb += color_component(ccid, v)
        return nmemb

    for u in range(n):
        if ccmap[u] < 0:
            ccmembs.append(color_component(len(ccmembs), u))

    for u in range(n):
        c = (ccmembs[ccmap[u]]
                - sum(1 for v in g[u] if ccmap[u] == ccmap[v])
                - sum(1 for v in bg[u] if ccmap[u] == ccmap[v])
                - 1)
        print(c, end=(' ' if u != n - 1 else '\n'))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    fs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    bs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]

    g = [[] for _ in range(n)]
    for u, v in fs:
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)

    bg = [[] for _ in range(n)]
    for u, v in bs:
        bg[u - 1].append(v - 1)
        bg[v - 1].append(u - 1)

    ccmembs = []
    ccmap = [-1] * n
    def color_component(ccid, root):
        stack = [root]
        ccmap[root] = ccid
        nmemb = 1
        while len(stack) > 0:
            u = stack.pop()
            for v in g[u]:
                if ccmap[v] < 0:
                    ccmap[v] = ccid
                    nmemb += 1
                    stack.append(v)
        return nmemb

    for u in range(n):
        if ccmap[u] < 0:
            ccmembs.append(color_component(len(ccmembs), u))

    for u in range(n):
        c = (ccmembs[ccmap[u]]
                - sum(1 for v in g[u] if ccmap[u] == ccmap[v])
                - sum(1 for v in bg[u] if ccmap[u] == ccmap[v])
                - 1)
        print(c, end=(' ' if u != n - 1 else '\n'))

if __name__ == '__main__':
    main()