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: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[-1]
from math import factorial
for i in range(m):
  l.append(int(input()))
l.append(n+1)
ans=1
is_False=0
for i in range(m+1):
  if l[i+1]-l[i]<2:
    is_False+=1
  elif l[i+1]-l[i]>=2:
    a,s=l[i+1]-l[i]-2,0
    for n in range(a//2+1):
      s+=factorial(a-n)/(factorial(n)*factorial(a-2*n))
    ans*=s%1000000007
    ans=ans%1000000007
print(ans if is_False==0 else 0)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[-1]
from math import factorial
for i in range(m):
  l.append(int(input()))
l.append(n+1)
ans=1
is_False=0
for i in range(m+1):
  if l[i+1]-l[i]<2:
    is_False+=1
  elif l[i+1]-l[i]>=2:
    a,s=l[i+1]-l[i]-2,0
    for n in range(a//2+1):
      s+=factorial(a-n)/(factorial(n)*factorial(a-2*n))
    ans*=s
    ans=ans%1000000007
print(ans if is_False==0 else 0)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[-1]
from math import factorial
for i in range(m):
  l.append(int(input()))
l.append(n+1)
ans=1
is_False=0
for i in range(m+1):
  if l[i+1]-l[i]<2:
    is_False+=1
  elif l[i+1]-l[i]>=2:
    a,s=l[i+1]-l[i]-2,0
    for n in range(a//2+1):
      s+=factorial(a-n)/(factorial(n)*factorial(a-2*n))
    ans*=s
print(ans%1000000007 if is_False==0 else 0)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
MOD = 1000000007

def a1b2(a, b):
    return ((math.factorial(a+b)) // (math.factorial(a) * math.factorial(b)))

def houhou(first, second):
    sa = second-first
    sum = 0
    if sa % 2 == 0:
        for b in range((sa // 2)+1):
            a = sa - 2*b
            sum += a1b2(a, b)
            sum = sum % MOD
    else:
        for b in range((sa // 2)+1):
            a = sa - 2 * b + 1
            sum+= a1b2(a, b)
            sum = sum % MOD
    return sum

a = input().split()
dan_num = int(a[0])
hole_num = int(a[1])
areas =[[0, None]]
holes = []
hole = None
before_hole = None
shippai = False
for i in range(hole_num):
    hole = int(input())
    areas[i][1] = hole-1
    areas.append([hole + 1, None])
    if before_hole == (hole -1) :
        shippai = True
    before_hole = hole
areas[-1][1] = dan_num

ways = 1
if dan_num == 1:
    print(1)
elif shippai:
    print(0)
else:
    for area in areas:
        ways *= houhou(area[0], area[1])
        ways = ways % MOD
    print(ways)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
MOD = 1000000007

def a1b2(a, b):
    return ((math.factorial(a+b)) // (math.factorial(a) * math.factorial(b)))

def houhou(first, second):
    sa = second-first
    sum = 0
    if sa % 2 == 0:
        for b in range((sa // 2)+1):
            a = sa - 2*b
            sum += a1b2(a, b)
            sum = sum % MOD
    else:
        for b in range((sa // 2)+1):
            a = sa - 2 * b + 1
            sum+= a1b2(a, b)
            sum = sum % MOD
    return sum

a = input().split()
dan_num = int(a[0])
hole_num = int(a[1])
areas =[[0, None]]
holes = []
hole = None
before_hole = None
shippai = False
for i in range(hole_num):
    hole = int(input())
    areas[i][1] = hole-1
    areas.append([hole + 1, None])
    if before_hole == (hole -1) :
        shippai = True
        break
    before_hole = hole
areas[-1][1] = dan_num

ways = 1
if dan_num == 1:
    print(1)
elif shippai:
    print(0)
else:
    for area in areas:
        ways *= houhou(area[0], area[1])
        ways = ways % MOD
    print(ways)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
MOD = 1000000007

def a1b2(a, b):
    return ((math.factorial(a+b)) // (math.factorial(a) * math.factorial(b)))

def houhou(first, second):
    sa = second-first
    sum = 0
    if sa % 2 == 0:
        for b in range((sa // 2)+1):
            a = sa - 2*b
            sum += a1b2(a, b)
            sum = sum % MOD
    else:
        for b in range((sa // 2)+1):
            a = sa - 2 * b + 1
            sum+= a1b2(a, b)
            sum = sum % MOD
    return sum

a = input().split()
dan_num = int(a[0])
hole_num = int(a[1])
areas =[[0, None]]
holes = []
hole = None
before_hole = None
shippai = False
for i in range(hole_num):
    hole = int(input())
    areas[i][1] = hole-1
    areas.append([hole + 1, None])
    if before_hole == (hole -1) :
        shippai = True
        break
    before_hole = hole
areas[-1][1] = dan_num

ways = 1
for area in areas:
    ways *= houhou(area[0], area[1])
    ways = ways % MOD
if dan_num == 1:
    print(1)
elif shippai:
    print(0)
else:
    print(ways)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
MOD = 10**9+7
a = set()
for i in range(M):
    a.add(int(input()))
step = [0]*(N+1)
step[0] = 1
for i in range(N+1):
    if i == 0:
        pass
    elif i in a:
        step[i] = 0
    elif i == 1:
        step[i] = step[0]
    else:
        step[i] = step[i-1]+step[i-2]
print(step[N])

Submission status: Wrong Answer

Solution code:
def dp(n):
    d=[0]*(n+1)
    if n==1:
        return 1
    else:
         d[0]=1
         if a[1]==0:
            d[1]=1
         else:
            d[1]=0
         for i in range(2,n+1):
            if a[i]==0:
                d[i]=d[i-1]+d[i-2]%1000000007
            else:
                d[i]=0
         return d[n]

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

Submission status: Wrong Answer

Solution code:
import sys


input = sys.stdin.readline

n, m = map(int, input().split())
broken = set()
for i in range(m):
    a = int(input())
    broken.add(a)

pattern = [0]*(n+1)
pattern[0] = 1

for i in range(2, n+1):
    if i in broken:
        pattern[i] = 0
    else:
        pattern[i] = pattern[i-1] + pattern[i-2]

print(pattern[n] % (10**9+7))

Submission status: Wrong Answer

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

dp=[0]*(N+1)
idx=0
dp[0]=1
if idx<M:
    if A[idx]==1:
        dp[1]=0
        idx+=1
else:
    dp[1]=1

for i in range(2,N+1):
    if idx<M:
        if A[idx]==i:
            dp[i]=0
            idx+=1
    else:
        dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
print(dp[-1])

Submission status: Wrong Answer

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

#通過できない階段をaに格納
a = [int(input()) for _ in range(m)]    
count = [0]*(n+1)
count[0] = 1
for i in range(2,n+1):
    if i in a:
        count[i] = 0
    else:
        count[i] = count[i-1]+count[i-2]        

print(count[-1]%(10**9+7))

Submission status: Wrong Answer

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

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n+1)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for index in range(n-2)[::-1]:
  i = index + 1
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

print(int(f[0]%div_num))

Submission status: Wrong Answer

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

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n+1)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-1)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

print(int(f[0]%div_num))

Submission status: Wrong Answer

Solution code:
n, m  = map(int, input().split())
f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
n,m = map(int,input().split())

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

for i in range(m):
    dp[int(input())] = -1

for i in range(m):
    if dp[i] != -1:
        if dp[i+1] != -1:
            dp[i+1] += dp[i]
        if dp[i+2] != -1:
            dp[i+2] += dp[i]

print(dp[n]%mod)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
n,m = map(int,input().split())
lst = [int(input()) for _ in range(m)]
dp = [0] * (n+2)

for i in range(n):
    if i in lst:
        continue
    if i==1:
        dp[i] += 1
    if i==2:
        dp[i] += 1
    if i+1 not in lst:
        dp[i+1] += dp[i]
    if i+2 not in lst:
        dp[i+2] += dp[i]

print(dp[n]%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# C - Typical Stairs

n, m = list(map(int, input().split()))
a_list = []

for _ in range(m):
    a = int(input().split()[0])
    a_list.append(a)

steps_list = [dict(fx1=True, fx2=True) for _ in range(n + 1)]

for step_index in a_list:
    steps_list[step_index] = dict(fx1=False, fx2=False)

    if step_index < n - 1:
        steps_list[step_index + 1]['fx1'] = False
    if step_index < n - 2:
        steps_list[step_index + 2]['fx2'] = False

p_count_list = [0] * (n + 1)

# fx段目に登る方法は、（fx-1 + fx-2）方法ある
# ただし、x-1が壊れている場合はfx-2通り
# x-2が壊れている場合はfx-1通り
for i, op in enumerate(steps_list):
    # print('step: {}'.format(i))
    if i in [0, 1]:
        p_count_list[i] = 1
        continue

    p_count = 0
    if steps_list[i]['fx1']:
        p_count += p_count_list[i-1]
    if steps_list[i]['fx2']:
        p_count += p_count_list[i-2]

    p_count_list[i] = p_count % 1000000007

# print(p_count_list)
ans = p_count_list[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_c
# C - Typical Stairs

n, m = list(map(int, input().split()))
a_list = []

for _ in range(m):
    a = int(input().split()[0])
    a_list.append(a)

steps_list = [dict(fx1=True, fx2=True) for _ in range(n + 1)]

for step_index in a_list:
    steps_list[step_index] = dict(fx1=False, fx2=False)

    if step_index < n - 1:
        steps_list[step_index + 1]['fx1'] = False
    if step_index < n - 2:
        steps_list[step_index + 2]['fx2'] = False

p_count_list = [0] * (n + 1)

# fx段目に登る方法は、（fx-1 + fx-2）方法ある
# ただし、x-1が壊れている場合はfx-2通り
# x-2が壊れている場合はfx-1通り
for i, op in enumerate(steps_list):
    # print('step: {}'.format(i))
    if i in [0, 1]:
        p_count_list[i] = 1
        continue

    p_count = 0
    if steps_list[i]['fx1']:
        p_count += p_count_list[i-1]
    if steps_list[i]['fx2']:
        p_count += p_count_list[i-2]

    p_count_list[i] = p_count

# print(p_count_list)
ans = p_count_list[-1] % 1000000007
print(ans)

Submission status: Wrong Answer

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

count = []
count.append(0)#使用しない
count.append(1)
count.append(2)

ans = 1

for i in range(3,n+1):
    if i in a:
        count.append(0)
        continue
    tmp1 = count[i-1]
    tmp2 = count[i-2]
    if tmp1 in a and tmp2 in a:
        ans = 0
        break
    elif tmp1 in a:
        count.append(tmp2)
    elif tmp2 in a:
        count.append(tmp1)
    else:
        count.append(tmp1 + tmp2)
if ans == 1:
    ans = count[n]
print(ans%1000000007)

Submission status: Wrong Answer

Solution 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())
a = [int(input(i)) for i in range(M)]
m = 0
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        break
    else:
        for j in range(M-1):
            dev = a[j+1]-a[j]
            m += Fib(dev)
        print(m)

Submission status: Wrong Answer

Solution code:
big = 10**9 + 7

def typical_stairs(n,m,a):

    route = [0]*(n+1)
    route[0] = 1
    ans = route[0]
    tmp = 0
    for j in range(m):
        for i in range(tmp,n):
            if a[j] == i+1:
                #print("a=%d, i+2=%d "%(a[j],i+2))
                route[i+1] = 0
                tmp = a[j]
            else:
                route[i+1] = route[i] + route[i-1]

                #print("route = %d, %d"%(i+1,ans))
        ans = route[i+1]
    return ans%big
if __name__ == '__main__':
    n,m = map(int,raw_input().split())
    a = [int(raw_input()) for _ in range(m)]

    print typical_stairs(n,m,a)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = list(int(input()) for i in range(M))
a.append(N+1)
a.insert(0,-1)
if a[0] == 0:
  print(0)
  exit()
#パターン数はフィボナッチ数列で通り数が増える
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
#aとa+1の間の距離nに対して、フィボナッチ数列n+1番目数のパターンが有る
ans = 1
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[0])%1000000007 * Fib(N-a[0])%1000000007)
elif M == 0:
    print(Fib(N+1)%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = list(int(input()) for i in range(M))
a.append(N+1)
if a[0] == 0:
  print(0)
  exit()
#パターン数はフィボナッチ数列で通り数が増える
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
#aとa+1の間の距離nに対して、フィボナッチ数列n+1番目数のパターンが有る
ans = 1
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[0])%1000000007 * Fib(N-a[0])%1000000007)
elif M == 0:
    print(Fib(N)%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = list(int(input()) for i in range(M))
a.append(N+1)

#パターン数はフィボナッチ数列で通り数が増える
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
#aとa+1の間の距離nに対して、フィボナッチ数列n+1番目数のパターンが有る
ans = 1
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1 #間の距離n
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n+1)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[0])%1000000007 * Fib(N-a[0])%1000000007)
elif M == 0:
    print(Fib(N)%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
a = list(int(input()) for i in range(M))
a.append(N+1)

#パターン数はフィボナッチ数列で通り数が増える
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
#aとa+1の間の距離nに対して、フィボナッチ数列n+1番目数のパターンが有る
ans = 1
print(M,a,N)
if M > 1:
    for i in range(len(a)-1):
        n = a[i+1]-a[i]-1 #間の距離n
        if n == 0:
            print(0)
            exit()
        ans = ans*Fib(n+1)%1000000007
        i += 1
    print(ans)
elif M == 1:
    print(Fib(a[0])%1000000007 * Fib(N-a[0])%1000000007)
elif M == 0:
    print(Fib(N)%1000000007)

Submission status: Wrong Answer

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

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

print(b)

num=max(b)

mod=1000000007

fib=[0 for i in range(num+10)]
print(fib)
fib[0]=1
fib[1]=1
for i in range(2,num+1):
    fib[i]=fib[i-1]+fib[i-2]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib[b[j]]
    print(p%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
lis=[]
ans=np.zeros(n+1)
ans[0]=1
for i in range(m):
    lis.append(int(input()))

if 1 not in lis:
    ans[1]=1

for i in range(n-1):
    if i+2 not in lis:
        ans[i+2]=ans[i]+ans[i+1]

print(ans[n]%(10**9+7))

Submission status: Wrong Answer

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

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

print(dp[-1]%1000000007)

Submission status: Wrong Answer

Solution code:
dp = [1] * (10**5 + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, 10**5):
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

n, m = map(int, input().split())
start = 0
res = 1
for i in range(m):
    nex = int(input())
    if nex == start:
        res = 0
        break
    res = (res * dp[(nex-1)-start]) % 1000000007
    #print('res :', res)
    start = nex + 1
else:
    res = (res * dp[n - start]) % 1000000007
    #print('res :', res)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(sys.stdin.readline()) for i in range(m)]
print(a)
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
   
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(j) for j in range(m)]
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
 
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit()
  
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)

Submission status: Wrong Answer

Solution code:
d = {}


def calc_step_combination(num):
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1
    if num in d:
        return d[num]
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    if len(a_list) == 0:
        print(0)
        return
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        result *= calc_step_combination(steps)
    print(result % 1000000007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()

Submission status: Wrong Answer

Solution code:
d = {}


def calc_step_combination(num):
    if num <= 0:
        return 0
    if num == 1 or num == 2:
        return 1
    if num in d:
        return d[num]
    res = calc_step_combination(num - 1) + calc_step_combination(num - 2)
    d[num] = res
    return res


def sol(n, a_list):
    if len(a_list) == 0:
        print(0)
        return
    step_batch = []
    batch_start = 0
    for a in a_list:
        step_batch.append(a - batch_start)
        batch_start = a + 1
    step_batch.append(n - batch_start + 1)

    result = 1
    for i, steps in enumerate(step_batch):
        result *= calc_step_combination(steps)
    print(result % 1000000007)


def main():
    n, m = map(int, input().split())
    a_list = []
    for i in range(0, m):
        a_list.append(int(input()))
    sol(n, a_list)


main()

Submission status: Wrong Answer

Solution code:
def main():
    tmp = list(map(int, input().split(" ")))
    n = tmp[0]
    m = tmp[1]

    if n == 1:
        print(1)
        return

    a = []
    for _ in range(m):
        a.append(int(input()))

    dp = [0 for _ in range(n+1)]
    dp[n] = 1
    dp[n-1] = 1

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

main()

Submission status: Wrong Answer

Solution code:
def main():
    tmp = list(map(int, input().split(" ")))
    n = tmp[0]
    m = tmp[1]
    
    if n == 1:
        print(1)
        return
    
    a = []
    for _ in range(m):
        a.append(int(input()))

    dp = [0 for _ in range(n+1)]
    dp[n] = 1
    dp[n-1] = 1

    for i in reversed(range(0, n-1)):
        if i in a:
            dp[i] = 0
        else:
            dp[i] = dp[i+1] + dp[i + 2]
    print(dp[0] % 1000000007)

main()

Submission status: Wrong Answer

Solution code:
def main():
    tmp = list(map(int, input().split(" ")))
    n = tmp[0]
    m = tmp[1]

    a = []
    for _ in range(m):
        a.append(int(input()))

    dp = [0 for _ in range(n+1)]
    dp[n] = 1
    dp[n-1] = 1

    for i in reversed(range(0, n-1)):
        if i in a:
            dp[i] = 0
        else:
            dp[i] = dp[i+1] + dp[i + 2]
    print(dp[0] % 1000000007)

main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))
ans = 0
flag = 0
  
#フィボナッチ数列の初期値を調節
dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
  
for i in range(2, n+1):
  if dp[i-2] == 0 and dp[i-1] == 0:
    ans = 0
    flag = 1
    break
  elif i in a:
    continue
  else:
    dp[i] = dp[i-1] + dp[i-2]
if flag == 0:
  ans = dp[n]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

n,m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
if len(a) >= 2:
    for i in range(m-1):
        if a[i]+1 == a[i+1]:
            print(0)
            exit()
def fib(n):
    a, b = 1, 0
    for _ in range(n):
        a, b = a + b, a
    return b

tmp = 0
ans = 1
for i in range(len(a)):
    ans *= fib(a[i]-tmp-1)
    tmp = a[i]+1
if tmp < n:
    ans *= fib(n-tmp)
print(ans%(10**9+7))

Submission status: Wrong Answer

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

bads = {}
for i in range(m):
    bads[int(input())] = None

dp = [1]
if 1 not in bads:
    dp.append(1)
else:
    dp.append(0)
for i in range(2, n):
    dp.append(0)
    if i-1 not in bads:
        dp[i] += dp[i-1]
    if i-2 not in bads:
        dp[i] += dp[i-2]
    dp[i] %= 1000000007

print(dp[-1])

Submission status: Wrong Answer

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

bads = {}
for i in range(m):
    bads[int(input())] = None

dp = [1, 1]
for i in range(2, n):
    dp.append(0)
    if i-1 not in bads:
        dp[i] += dp[i-1]
    if i-2 not in bads:
        dp[i] += dp[i-2]
    dp[i] %= 1000000007

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import math
def conbination(x,y):
  return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))
 
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

flag = 0
ans = 0
 
for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m): #i:２段のぼる回数
    if i>=m:
  	  ans += conbination(n-2*m-1, i-m) * conbination(n-m, m)
      
print(ans%(10**9+7))

Submission status: Wrong Answer

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

bads = []
for i in range(m):
    bads.append(int(input()))

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import math
def conbination(x,y):
  return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))
 
n, m = map(int, input().split())
a = []
for i in range(m):
  a.append(int(input()))

flag = 0
ans = 0
 
for i in range(m-1):
  if a[i+1] - a[i] == 1:
    ans = 0
    flag = 1
    break
    
if flag == 0:
  for i in range(n-2*m-1): #i:２段のぼる回数
    ans += conbination(n-2*m-2, i)
      
print(ans%(10**9+7))

Submission status: Wrong Answer

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

dp = [0] * (N+1)
dp[0] = 1
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1
div = 1000000007

for i in range(2,N+1):
  if (dp[i-1] == 0) & (dp[i-2]==0):
    print(0)
    exit()
  elif i in A:
    continue
  else:
    dp[i] = dp[i-1]+dp[i-2]

print(dp[N])

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(n-1):
  if i not in a:
    b[i+1]+=b[i]
    b[i+2]+=b[i]
  else:
    b[i]=0

if n not in a:
  b[n]+=b[n-1]

print(b[n]%(10**9+7))

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
x =  1000000007

p,q=(0,1)

for i in range(1, n+1):
	p,q = q,(p+q)*(not i in a)
print(q)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))
    
def fibonacci(n):
    listf = [0]+[1]*n
    a, b = 1, 0
    for i in range(n-1):
        a, b = (a+b)%1000000007 , a
    listf[i+2] = a
    return listf 

fib = fibonacci(N+1)

if a:
    ans = [a[0]]
    
    for i in range(M-1):
        ans.append(a[i+1]-a[i]-1)
            

    result = 1
    for j in range(len(ans)):
        result = result * fib[ans[j]] % 1000000007
    
    result = result * fib[(N - a[-1])] % 1000000007
    
    print(result)
else:
    ans = fib[-1]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
INF = (10 ** 9) + 5
N, M = map(int, input().split())
aLst = [0] * M

for i in range(M):
    aLst[i] = int(input())
ansLst = [0] * (N + 1)
ans = 0
ansLst[0] = 1
for i in range(1, N + 1):
    if aLst.count(i) == 1:
        continue
    tmp = ansLst[i - 1]
    if i > 1:
        tmp += ansLst[i - 2]
    ansLst[i] = tmp % INF


print(ansLst[N])

Submission status: Wrong Answer

Solution code:
import sys
INF = (10 ** 9) + 5
N, M = map(int, input().split())
aLst = [0] * M

for i in range(M):
    aLst[i] = int(input())
ansLst = [0] * N
ans = 0
cnt = 0
for i in range(N):
    if i == 0:
        if aLst.count(1) == 0:
            ansLst[0] = 1
    elif i == 1:
        if aLst.count(2) == 0:
            ansLst[1] = 1 + ansLst[0]
    elif aLst.count(i + 1) != 1:
        ansLst[i] = (ansLst[i - 2] + ansLst[i - 1]) % INF
    else:
        cnt += 1
    if cnt == 2:
        print(0)
        sys.exit()
    cnt = 0

print(ansLst[-1])

Submission status: Wrong Answer

Solution code:
import sys
INF = (10 ** 9) + 5
N, M = map(int, input().split())
aLst = [0] * M

for i in range(M):
    aLst[i] = int(input())
ansLst = [0] * N
ans = 0

for i in range(N):
    if i == 0:
        if aLst.count(1) == 0:
            ansLst[0] = 1
    elif i == 1:
        if aLst.count(2) == 0:
            ansLst[1] = 1 + ansLst[0]
    elif aLst.count(i + 1) != 1:
        ansLst[i] = ansLst[i - 2] + ansLst[i - 1]
cnt = 0
for i in ansLst:
    if i == 0:
        cnt += 1
    else:
        cnt = 0
    if cnt == 2:
        print(0)
        sys.exit()

print(ansLst[-1] % INF)

Submission status: Wrong Answer

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

if M == 0:
    maxM = N
else:
    maxM = a[0] - 1
    for i in range(1, M):
        maxM = max(maxM, a[i] - a[i-1] - 2)
    maxM = max(maxM, N - a[-1])

dp = [0] * (maxM+1)
dp[1] = 1
if maxM > 1:
    dp[2] = 2
    if maxM > 2:
        for n in range(3, maxM+1):
            dp[n] = dp[n-1] + dp[n - 2] % 1000000007

if M == 0:
    print(dp[-1])
    exit()

if a[0] == 1:
    ans = 1
else:
    ans = dp[a[0] - 1]

if M > 1:
    for i in range(1, M):
        if a[i] - a[i - 1] == 1:
            ans = 0
        elif a[i] - a[i - 1] == 2:
            continue
        else:
            ans = ans * dp[a[i] - a[i - 1] - 2] % 1000000007
if N - a[-1] != 1:
    ans = ans * dp[N - a[-1] - 1] % 1000000007
print(ans)

Submission status: Wrong Answer

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

if M == 0:
    maxM = N
else:
    maxM = a[0] - 1
    for i in range(1, M):
        maxM = max(maxM, a[i] - a[i-1] - 2)
    maxM = max(maxM, N - a[-1])

dp = [0] * (maxM+1)
dp[1] = 1
if maxM > 1:
    dp[2] = 2
    if maxM > 2:
        for n in range(3, maxM+1):
            dp[n] = dp[n-1] + dp[n - 2] % 1000000007

if M == 0:
    print(dp[-1])
    exit()

if a[0] == 1:
    ans = 1
else:
    ans = dp[a[0] - 1]

if M > 1:
    for i in range(1, M):
        if a[i] - a[i - 1] <= 1:
            ans = 0
        else:
            ans = ans * dp[a[i] - a[i - 1] - 2] % 1000000007
if N - a[-1] != 1:
    ans = ans * dp[N - a[-1] - 1] % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0] * 10*(N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i == N or i == N-1:
        dp[i] = 1
    elif i in a:
        continue
    else:
        dp[i] = dp[i+1] + dp[i+2]
print(dp[0]%mod)

Submission status: Wrong Answer

Solution code:
import sys

N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
c=[0]*(N+1)
c[0]=1
MOD=7+10**9
if M==0:
    c[1]=1
    for i in range(1,N):
        c[i+1]=c[i]+c[i-1]
    print(c[N])
elif N==1:
    print(1)
else:
    j=0
    for i in range(1,N):
        if i==a[j]:
            if j+1<M:
                if i+1==a[j+1]:
                    print(0)
                    sys.exit(0)
                else:
                    j+=1
        elif i==2:
            c[i]=c[i-1]
        else:
            c[i]=(c[i-1]+c[i-2])%MOD
    print(c[-1]%MOD)

Submission status: Wrong Answer

Solution code:
import sys

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