Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Accepted

Solution code:
#ABC129 C
N, M = (int(_) for _ in input().split())
a = [0 for i in range(M)]
MOD = 10 ** 9 + 7
for i in range(M):
    a[i] = int(input())
a.append(0)
dp = [0 for i in range(N + 1)]
j = 0
for i in range(N + 1):    
    if i == a[j] and M != 0:
        j += 1
    elif i == 0:
        dp[i] = 1
    elif i == 1:
        dp[i] = 1
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
print(dp[N] % MOD)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
broken = set(a)
dp=[0]*(n+1)
mod = 10**9 + 7

for i in range(n,-1,-1):
  if i in broken:
    continue
  elif i==n or i==n-1:
    dp[i]=1
  else:
    dp[i]=dp[i+1]+dp[i+2]
print(dp[0]%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
broken = set(a)
dp=[0]*(n+1)
mod = 10**9 + 7

for i in range(n,-1,-1):
  if i in broken:
    continue
  elif i==n or i==n-1:
    dp[i]=1
  else:
    dp[i]=dp[i+1]+dp[i+2]
    dp[i]=dp[i]%mod
print(dp[0])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
broken = set(a)
dp=[0]*(n+1)
mod = 10**9 + 7

for i in range(n,-1,-1):
  if i in broken:
    continue
  elif i==n or i==n-1:
    dp[i]=1
  else:
    dp[i]=dp[i+1]+dp[i+2]
    dp[i]%=mod
print(dp[0])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
broken = set(a)
dp=[0]*(n+1)
mod = 10**9 + 7
for i in range(n,-1,-1):
  if i in broken:
    continue
  else:
    if i==n or i==n-1:
      dp[i]=1
    else:
      dp[i]=dp[i+1]+dp[i+2]
print(dp[0]%mod)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a = [int(input()) for i in range(m)]
dp=[0]*(n+1)
if m==0:
  for i in range(n,-1,-1):
    if i==n or i==n-1:
      dp[i]=1
    else:
      dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)
else:
  j=-1
  for i in range(n,-1,-1):
    if i==a[j]:
      if m>j*(-1):
        j-=1
    else:
      if i==n or i==n-1:
        dp[i]=1
      else:
        dp[i]=dp[i+1]+dp[i+2]
  print(dp[0]%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 1000000007


def main():
    n, m = list(map(int, input().split()))
    stairs = defaultdict(lambda: True)
    for i in range(m):
        a = int(input())
        stairs[a] = False

    dp = defaultdict(lambda: 0)
    dp[0] = 1

    for i in range(1, n + 1):
        if stairs[i]:
            dp[i] = dp[i - 1] + dp[i - 2]
            dp[i] %= MOD

    print(dp[n])


main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
j = 0
dp = [0] * 100100
dp[0] = 1
for i in range(1,N+1):
    if j < M and i == A[j]:
        j += 1
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 10**9+7
print(dp[N])

Submission status: Accepted

Solution code:
n,m = map( int, input().split() )

a = [-1]
for i in range(m):
    a.append(int(input()))
a.append(n+1)
m += 1

ans = 1
for i in range(m):
    if a[i+1]-a[i]-1 == 0:
        ans = 0
        break
    elif a[i+1]-a[i]-1 == 1:
        continue
    else:
        dp = [1] + [0]*(a[i+1]-a[i]-2)
    for j in range(1, a[i+1]-a[i]-1):
        dp[j] = dp[j-1] + dp[j-2]
    ans *= dp[-1]

print(ans%1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xs = [int(input()) for _ in range(m)]

broken = [False] * (n + 1)
for x in xs:
    broken[x] = True

cache = [-1] * (n + 1)

def solve(pos, n, broken, cache):
    if pos > n or broken[pos]:
        return 0
    if pos == n:
        return 1
    res = cache[pos]
    if res >= 0:
        return res
    res = solve(pos+1, n, broken, cache) + solve(pos+2, n, broken, cache)
    cache[pos] = res = res % 1000000007
    return res

for tmp in range(n,0,-1):
    solve(tmp,n,broken,cache)

print(solve(0,n,broken,cache))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 1000000007

broken = [0] * N
for i in range(M):
    broken[int(input())] = 1


dp = [0] * (N + 2)
dp[N] = 1
for i in reversed(range(N)):
    if broken[i]:
        dp[i] = 0
        continue
    dp[i] = dp[i+1] + dp[i+2]

print(dp[0] % MOD)

Submission status: Accepted

Solution code:
N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)

Submission status: Accepted

Solution code:
N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
bs = [-1]
for i in range(m):
    bs.append(int(input()))
bs.append(n + 1)

cs = []
for i in range(m + 1):
    c = bs[i+1] - bs[i] - 2
    if (c < 0):
        print(0)
        exit()
    cs.append(bs[i+1] - bs[i] - 2)
mc = max(cs)

ds = [1, 1, 2]
for i in range(mc + 1):
    if i < 3:
        continue
    ds.append(ds[i-1] + ds[i-2])

r = 1
for c in cs:
    r *= ds[c]

print(r % 1000000007)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = set([_I() for i in range(M)])

#  if M != 0:
#      # 連続した壊れた段がある場合は0
#      B = [i for i in A]
#      B.remove(B[0])
#      B.append(10**15+100)
#      diffs = [b - a for a, b in zip(A,B)]
#      #  print(diffs)

#      if any(i == 1 for i in diffs):
#          # 隣同士なので0
#          print(0)
#          exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
#  dp = {}
dp = [0 for i in range(N+1)]
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
#  [dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
for i in range(2, N+1):
    #  print(i)
    # i段目までの通りを計算する
    if i not in A:
        # i段目が障害のときは0になっているので飛ばす
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= mod

print(dp[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

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

print(dp[-1])

Submission status: Accepted

Solution code:
mod = 1000000007
N,M = list(map(int,input().split()))

b = [0]*(N+2)
b[0]=1

for i in range(M):
    b[int(input())] = -1

for i in range(N):
    if b[i] != -1:
        if b[i+1] != -1:
            b[i+1] += b[i]
        if b[i+2] != -1:
            b[i+2] += b[i]
print(b[N]%mod)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0] * M
for i in range(M):
    a[i] = int(input())


dp = [0] * (N+1)

for i in range(N+1):
    if i == 0:
        dp[i] = 1
    elif i == 1:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = 1
        else:
            dp[i] = 1
    else:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = dp[i-1] + dp[i-2]
                dp[i] = dp[i] % 1000000007
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i] % 1000000007

ans = dp[N]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#ABC130C
import sys


tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
m=hoge[1]

a=[]
for i in range(0,n):
	a.append(1)

#print(a)

for i in range(0,m):
	tmp = int(input())
	a[tmp]=0

#print(a)


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


if(n==1):
	print(1)
else:
	print((a[n-1]+a[n-2])% 1000000007)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:dp[i]=0
print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
inputs = [int(input()) for _ in range(M)]

set_inputs = set(inputs)
mod = 10 ** 9 + 7
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(1, N+1):
    if i in set_inputs:
        continue
    if i == 1:
        dp[i] = dp[i-1]
    else:
        if i - 1 not in set_inputs:
            dp[i] += dp[i-1]
        if i - 2 not in set_inputs:
            dp[i] += dp[i-2]

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
from copy import *
from sys import *
import math
import queue
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	fib = [0,1,1,2]
	for i in range(3,10**5+100):
		fib.append(fib[i-1]+fib[i])
	n,m = map(int,input().split())
	last = 0
	ans = 1
	a =  []
	for i in range(m):
		a.append(int(input()))
	for t in a:
		ans *= fib[t-last]
		last =  t+1
	ans *= fib[n-last+1]
	print(ans%(10**9+7))


def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Submission status: Accepted

Solution code:
n, m = [int(_) for _ in input().split()]
a = [-1]
for i in range(m):
    a.append(int(input()))
a.append(n+1)

m = len(a)

diffs = []
for i in range(m-1):
    diffs.append(a[i + 1] - a[i] - 2)
diffs.sort()

fibs = []
for i in range(0, max(diffs) + 1):
    if i == 0:
        fibs.append(1)
    elif i == 1:
        fibs.append(1)
    else:
        fibs.append(fibs[-1] + fibs[-2] % 1000000007)

def func(k):
    if (k == -2):
        return 1
    elif (k == -1):
        return 0
    else:
        return fibs[k]

ans  = 1
for i in range(len(diffs)):
    ans = ans * func(diffs[i]) % 1000000007

print(ans)

Submission status: Accepted

Solution code:
# 解き直し
# 名前にTypicalって書いてあるのでTypicalです


n, m = map(int, input().split())
step_count = [0 for _ in range(n+1)]
ng_step = [False for _ in range(n+1)]
for _ in range(m):
  ng = int(input())
  ng_step[ng] = True

for i in range(n+1):
  if ng_step[i]:
    step_count[i] = 0
  else:
    if i==1:
      step_count[i] = 1
    elif i==2:
      step_count[i] = 1 + step_count[i-1]
    else:
      step_count[i] = (step_count[i-2]+step_count[i-1])%(10**9+7)

print(step_count[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = {int(input()) for _ in range(m)}
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n+1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
    if i in a: dp[i] = 0
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = {int(input()) for _ in range(m)}
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n+1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % (10 ** 9 + 7)
    if i in a: dp[i] = 0
print(dp[n])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

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

for _ in range(m):
    broken[int(input())] = 1

dp[0] = 1

if broken[1] == 1:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n+1):
    if broken[i] == 1:
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

print(dp[n])

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
As = set()
for i in range(0, M):
    As.add(int(input()))
C = 10 ** 9 + 7

dp = [0 for _ in range(N + 1)]
dp[0] = 1
dp[1] = 0 if 1 in As else 1

for i in range(2, N + 1):
    if i in As:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % C

print(dp[N])

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=[int(input()) for i in range(m)]
 
dp=['inf']*(n+1)
dp[0]=1
dp[1]=1
for i in range(m):
    dp[a[i]]=0

for i in range(2,n+1):
    if dp[i]==0:
        if dp[i+1]==0:
            print(0)
            exit()
        else:
            pass
    else:
        dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%(10**9+7))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
a = [ int(input()) for i in range(M)]
Sum = [0]*(N+1)
Sum[0] = 1
Judge = [True]*(N+1)
for i in range(M):
    Judge[a[i]] = False
for k in range(1,N+1):
    if Judge[k]:
        Sum[k] = Sum[k-1] + Sum[k-2]
    else:
        Sum[k] = 0
print(Sum[N]%1000000007)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = set()
for i in range(m):
  l.add(int(input()))

ans = [0]*(n+1)
for j in range(n+1):
  if j in l:
    ans[j] = 0
  else:
    if j == 0:
      ans[j] = 1
    elif j == 1:
      ans[j] = ans[j-1]
    else:
      ans[j] = ans[j-1] + ans[j-2]
print(ans[-1]%1000000007)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))
dp = []
dp.append(1)
if m == 0:
    a.append(-1)
j = 0
k = len(a)-1
if 1 == a[j]:
    dp.append(0)
    j = min(k,j+1)
else:
    dp.append(1)

for i in range(2,n+1):
    if i == a[j]:
        dp.append(0)
        j = min(k,j+1)
    else:
        dp.append(dp[i-1] + dp[i-2])

print(dp[n]%(1000000007))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

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

print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a,b,c = LI()
    ans = 10 ** 5
    ans = min(ans, a + b)
    ans = min(ans, a + c)
    ans = min(ans, c + b)
    print(ans)
    return

#B
def B():
    n = II()
    w = LI()
    ans = inf
    for i in range(n):
        ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))
    print(ans)
    return

#C
def C():
    n, m = LI()
    a = IR(m)+[inf]
    dp = [0] * (n + 3)
    dp[0] = 1
    for i in range(n + 1):
        if a[bisect_left(a, i + 1)] != i + 1:
            dp[i + 1] += dp[i] % mod
        if a[bisect_left(a, i + 2)] != i + 2:
            dp[i + 2] += dp[i] % mod
    print(dp[n] % mod)
    return

#D
def D():
    return


#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(int(input()) for i in range(m))

mod = 1000000007
b = [0]*(m + 1)
if m != 0:
    b[0] = a[0] - 1
    b[m] = n - a[m - 1] - 1
else:
    b[0] = n

for i in range(1,m):
    b[i] = a[i] - a[i-1] - 2

b.sort()
ans = 1
if b[0] == -1:
    ans = 0
else:
    pattern = [0]*(max(b[m]+1,2))
    pattern[0] = 1
    pattern[1] = 1
    for i in range(2,b[m]+1):
        pattern[i] = pattern[i-1] + pattern[i-2]
    for i in range(m + 1):
        ans *= pattern[b[i]]

print(ans % mod)