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:
MOD = 10**9+7
n, m = map(int, input().split())
broken = [False for _ in range(n+1)]
dp = [0 for _ in range(n+1)]
dp[0] = 1
for _ in range(m):
	broken[int(input())] = True
for i in range(1, n+1):
	if broken[i]:
		continue
	if i == 1:
		dp[i] = dp[i-1]
	else:
		dp[i] = dp[i-1] + dp[i-2]
		dp[i] %= MOD
print(dp[n])

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

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

#C
def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+10)]
    dp[0] = 1
    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    h,w = LI()
    s = SR(h)

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10 ** 9 + 7

arrs = set([int(input()) for _ in range(M)])
anss = [0, 1]
for i in range(1, N+1):
  if i in arrs:
    anss.append(0)
  else:
    anss.append((anss[-2] + anss[-1]) % MOD)
print(anss[-1] % MOD)

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    p,q,r = LI()
    print(p+q+r-max(p,q,r))
    return

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

#C
def C():
    n,m = LI()
    f = defaultdict(lambda : 1)
    for i in range(m):
        a = I()
        f[a] = 0
    dp = [0 for i in range(n+1)]
    dp[0] = 1
    for i in range(1,n+1):
        if f[i]:
            dp[i] = dp[i-1]+dp[i-2]
            dp[i] %= mod
    print(dp[n])
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0]=1
a=[int(input()) for i in range(M)]
isbroken=[1 for i in range(N+1)]
for i in range(M):
    isbroken[a[i]]=0
for i in range(N):
    if i-1>=0:
        dp[i+1]=dp[i]*isbroken[i]+dp[i-1]*isbroken[i-1]
    else:
        dp[i+1]=dp[i]*isbroken[i]
    dp[i+1]%=mod
print(dp[N])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i,n) for (int i = 1; i <= (int)(n); i++)

int main()
{
  int n,m;
  cin >> n >> m;
  
  int a[m];
  cin >> a[0];
  for(int i = 1; i < m; i++)
  {
    cin >> a[i];
    if(a[i] == a[i-1]+1)
    {
      cout << 0 << endl;
      return 0;
    }
  }
  
  int f[n+1];
  ll mod = 1000000007;
  f[0] = 1; f[1] = 1;
  for(int i = 2; i <= n; i++)
  {
    f[i] = f[i-1] + f[i-2];
    f[i] %= mod;
  }
  
  ll ans = 1;
  ll now = 0;
  ll up = 0;
  for(int i = 0; i < m; i++)
  {
    up = a[i] - now;
    ans = (ans % mod) * (f[up-1] % mod);
    ans %= mod;
    now = a[i]+1;
  }
  up = n - now;
  ans *= f[up];
  
  ans %= mod;
  cout << ans << endl;

}

Submission status: Runtime Error

Solution code:
#ABC129 C

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

B = [1,2]
for i in range(N):
    B.append(B[i]+B[i+1])
    
C = [B[A[j]-A[j-1]-3] for j in range(1,M)]
print((sum(C)+B[A[0]-2]+B[N-A[M-1]-2])%(1000000007))

Submission status: Runtime Error

Solution code:
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]
    inf = 10**9+7

    #動的計画法問題
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    else:
        dp[1] = 0

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

    print(dp[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [int(input()) for i in range(M)]
inf = 10**9+7

#動的計画法問題
dp = [0] * (N+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0

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

print(dp[N])

Submission status: Runtime Error

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

#動的計画法問題
dp = [0] * (N+1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
  else:
    dp[1] = 0

    for i in range(2,N+1):
      if i in a:
        continue
        dp[i] = dp[i-1] + dp[i-2]

        dp[i] %= (10**9+7)

print(dp[N])

Submission status: Runtime Error

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

dp = [0]*(N+1)

def stair(x):
    if(x in a):
        dp[x] = 0
        return 0
    if(x == 1 and x not in a):
        dp[x] = 1
        return 1
    if(x == 0):
        dp[x] = 1
        return 1
    if(dp[x] != 0):
        return dp[x]
    dp[x] = stair(x-1) + stair(x-2)
    return dp[x]
        
print(stair(N) % (10**9 + 7))

Submission status: Runtime Error

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

dp = [0]*(N+1)

def stair(x):
    if(x in a):
        dp[x] = 0
        return 0
    if(x == 1 and x not in a):
        dp[x] = 1
        return 1
    if(x == 0):
        dp[x] = 1
        return 1
    if(dp[x] != 0):
        return dp[x]
    dp[x] = stair(x-1) + stair(x-2)
    return dp[x]
        
print(stair(N) % 1000000007)

Submission status: Runtime Error

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

dp = [0]*(N+1)

def stair(x):
    if(x in a):
        dp[x] = 0
        return 0
    if(x == 1 and x not in a):
        dp[x] = 1
        return 1
    if(x == 0):
        dp[x] = 1
        return 1
    if(dp[x] != 0):
        return dp[x]
    dp[x] = stair(x-1) + stair(x-2)
    return dp[x]
        
print(stair(N) % 1000000007)

Submission status: Runtime Error

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

for i in range(M):
    broken[a[i]] = 1

dp = [0]*(N+1)

def stair(x):
    if(broken[x] == 1):
        dp[x] = 0
        return 0
    if(x == 1 and broken[x] == 0):
        dp[x] = 1
        return 1
    if(x == 0):
        dp[x] = 1
        return 1
    if(dp[x] != 0):
        return dp[x]
    dp[x] = stair(x-1) + stair(x-2)
    return dp[x]
        
print(stair(N) % 1000000007)

Submission status: Runtime Error

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

dp = [1]
t = 0
if 1==li[t]:
    t += 1
    dp += [0]
else:
    dp += [1]
for i in range(2,n+1):
    if i == li[t]:
        dp = [dp[1],0]
        if t<m-1:t += 1
        continue
    dp = [dp[1]%mod,(dp[0]+dp[1])%mod]
print(dp[1])

Submission status: Runtime Error

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

if not a[1]:
    dp[1]=1

if not a[2]:
    dp[2]=dp[1]+1

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

print(dp[n]%mod)

Submission status: Runtime Error

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

dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    dp[i]=dp[i-1]+dp[i-2]
    dp[i]%=mod

begin=0
end=a[0]-1
for i in range(m):
    end=a[i]-1
    ans*=dp[end-begin]
    
    if(i+1<m and a[i+1]==a[i]+1):
        ans=0
        break
        
    else:
        begin=end+2

ans*=dp[n-a[m-1]-1]

print(ans%mod)

Submission status: Runtime Error

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

if M != 0:
  for _ in range(M):
    A.append(int(input()))

#初期化
dp=[0]*N
if A.count(1) == 0:
  dp[0]=1
if A.count(1) == 0 and A.count(2) == 0:
  dp[1]=2
elif A.count(1) ==1 and A.count(2) ==0:
  dp[1]=1

#dp
if N >= 3:
  for i in range(N-2):
    if A.count(i+3) ==1:
      dp[i+2] = 0
    elif A.count(i+1) == 0 and A.count(i+2) == 0:
      dp[i+2] = dp[i+1] + dp[i]
    elif A.count(i+1) == 0 and A.count(i+2) == 1:
      dp[i+2] = dp[i]
    elif A.count(i+1) == 1 and A.count(i+2) == 0:
      dp[i+2] = dp[i+1]
    else:
      dp[i+2] = 0
      
print(dp[N-1]%1000000007)

Submission status: Runtime Error

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

for _ in range(M):
  A.append(int(input())-1)

#初期化
dp=[0]*N
if A.count(0) == 0:
  dp[0]=1
if A.count(0) == 0 and A.count(1) == 0:
  dp[1]=2
elif A.count(0) ==1 and A.count(1) ==0:
  dp[1]=1

#dp
if N >= 3:
  for i in range(N-2):
    if A.count(i+2) ==1:
      dp[i+2] = 0
    elif A.count(i) == 0 and A.count(i+1) == 0:
      dp[i+2] = dp[i+1] + dp[i]
    elif A.count(i) == 0 and A.count(i+1) == 1:
      dp[i+2] = dp[i]
    elif A.count(i) == 1 and A.count(i+1) == 0:
      dp[i+2] = dp[i+1]
    else:
      dp[i+2] = 0
      
print(dp[N-1]%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
a = list(int(input()) for _ in range(m))
dp = [[] for _ in range(n + 1)]
dp[0] = 1
# j = 0
if m = 0:
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    print(dp[n])
    exit()
if a[0] == 1:
    dp[1] = 0
    j = 1
else:
    dp[1] = 1
    j = 0
for i in range(2, n + 1):
    # print(i, dp)
    if j < m:
        if a[j]  == i:
            dp[i] = 0
            j += 1
            continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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


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

print(memo[-1]%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def kaidan(n):
    global memo
    if memo[n]==0:
        if n == 1 or n == 0:
            memo[n] = 1
        else:
            memo[n] = kaidan(n-1)+kaidan(n-2)
    return memo[n]%1000000007

memo = [0] * (10**5 + 1)

n,m = map(int,input().split())
start = 0
ans = 1
for i in range(m):
    a = int(input())
    if start == a:
        ans = 0
        break
    else:
        ans = (ans * kaidan((a-1)-start))%1000000007
        start = a + 1
ans = ans * kaidan(n-start)
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
NG=[0]*10**5
for i in range(m):
    NG[A[i]]=1
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

@lru_cache(maxsize=10**10)
def qwe(x):
    if x==n:return 1
    if x>n:return 0
    if NG[x+1] and NG[x+2]: print(0);exit()
    if NG[x+1]:return qwe(x+2)%mod
    if NG[x+2]:return qwe(x+1)%mod
    return (qwe(x+2)+qwe(x+1))%mod
print(qwe(0))

Submission status: Runtime Error

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

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

if 1 not in a:
    dp[1] = 1
else:
    dp[1] = 0

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

print(dp[n])

Submission status: Runtime Error

Solution code:
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])

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
dp = [0]*(n+1)
dp[1],dp[2] = 1,1

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

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

Submission status: Runtime Error

Solution code:
import sys
import functools
import operator
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]

if n==2 and m==1:
  print('1')
  sys.exit()
    
if n==1:
  if m==0:
    print('1')
    sys.exit()
  else:
    print('0')

def s(x):
    if x==1 or x==0:
        return 1
    if x==2:
        return x
    return s(x-1)+s(x-2)
    
if m==0:
  print(s(n))
  sys.exit()

c=[]

p=s(a[0]-1)
c.append(p)

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()
  else:
    q=s(a[i]-a[i-1]-2)
    c.append(q)
  
r=s(n-(a[m-1]+1))
c.append(r)

ans=functools.reduce(operator.mul,c)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import sys
import functools
import operator
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]

if n==2 and m==1:
  print('1')
  sys.exit()

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()
    
if n==1:
  if m==0:
    print('1')
    sys.exit()
  else:
    print('0')

def s(x):
    if x==1 or x==0:
        return x
    if x==2:
        return x
    return s(x-1)+s(x-2)
    
if m==0:
  print(s(n))
  sys.exit()

c=[]

p=s(a[0]-1)
c.append(p)

for i in range(1,m):
  q=s(a[i]-a[i-1]-2)
  c.append(q)
  
r=s(n-(a[m-1]+1))
c.append(r)

ans=functools.reduce(operator.mul,c)
print(ans%(10**9+7))

Submission status: Runtime Error

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

if n==2 and m==1:
  print('1')
  sys.exit()

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()
    
if n==1:
  if m==0:
    print('1')
    sys.exit()
  else:
    print('0')

def s(x):
    if x==1 or x==0:
        return x
    if x==2:
        return x
    return s(x-1)+s(x-2)
    
if m==0:
  print(s(n))
  sys.exit()

c=[]


for i in range(m):
  if i==0:
    p=s(a[i]-1)
    c.append(p)
  else:
    q=s(a[i]-a[i-1])
    c.append(q)
  r=s(n-(a[m-1]+1))
  c.append(r)

print(sum(c)%(10**9+7))

Submission status: Runtime Error

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

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()
    
if n==1:
  print('1')
  sys.exit()

def s(x):
    if x==1 or x==0:
        return x
    if x==2:
        return x
    return s(x-1)+s(x-2)
    
if m==0:
  print(s(n))
  sys.exit()

c=[]


for i in range(m):
  if i==0:
    p=s(a[i]-1)
    c.append(p)
  else:
    q=s(a[i]-a[i-1])
    c.append(q)
  r=s(n-(a[m-1]+1))
  c.append(r)

print(sum(c)%(10**9+7))

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
M=int(r[1])
data_pre=[input() for i in range(M)]
data=[int(s) for s in data_pre]
def func(num):
    if num<=2:
        return 1
    else:
        return int((((1+5**(1/2))/2)**num-((1-5**(1/2))/2)**num)/(5**(1/2)))
if N%2==0 and M>int(N/2):
    print(0)
elif N%2==1 and M>int((N+1)/2):
    print(0)
else:
    ans=1
    mark=0
    if M>=2:
        for i in range(1,M):
            if data[i]-data[i-1]==1:
                ans=0
                mark+=1
                print(ans)
                break
            else:
                x=data[i]-data[i-1]-1
                y=func(x)
                ans=ans*y
        if mark==0:
            x=N-data[M-1]
            y=func(x)
            X=data[0]
            Y=func(X)
            ans=ans*y*Y
            print(ans%(10**9+7))
    elif M==1:
        x=N-data[0]
        y=func(x)
        X=data[0]
        Y=func(X)
        ans=ans*y*Y
        print(ans%(10**9+7))
    else:
        print(func(N+1)%(10**9+7))

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
M=int(r[1])
data_pre=[input() for i in range(M)]
data=[int(s) for s in data_pre]
def func(num):
    if num<=2:
        return num
    else:
        return int((((1+5**(1/2))/2)**num-((1-5**(1/2))/2)**num)/(5**(1/2)))
if N%2==0 and M>int(N/2):
    print(0)
elif N%2==1 and M>int((N+1)/2):
    print(0)
else:
    ans=1
    mark=0
    if M>=2:
        for i in range(1,M):
            if data[i]-data[i-1]==1:
                ans=0
                mark+=1
                print(ans)
                break
            else:
                x=data[i]-data[i-1]-1
                y=func(x)
                ans=ans*y
        if mark==0:
            x=N-data[M-1]
            y=func(x)
            X=data[0]
            Y=func(X)
            ans=ans*y*Y
            print(ans%(10**9+7))
    elif M==1:
        x=N-data[0]
        y=func(x)
        X=data[0]
        Y=func(X)
        ans=ans*y*Y
        print(ans%(10**9+7))
    else:
        print(func(N+1)%(10**9+7))

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
M=int(r[1])
data_pre=[input() for i in range(M)]
data=[int(s) for s in data_pre]
def func(num):
    if num<=2:
        return 1
    else:
        return int((((1+5**(1/2))/2)**num-((1-5**(1/2))/2)**num)/(5**(1/2)))
if N%2==0 and M>int(N/2):
    print(0)
elif N%2==1 and M>int((N+1)/2):
    print(0)
else:
    ans=1
    mark=0
    if M>=2:
        for i in range(1,M):
            if data[i]-data[i-1]==1:
                ans=0
                mark+=1
                print(ans)
                break
            else:
                x=data[i]-data[i-1]-1
                y=func(x)
                ans=ans*y
        if mark==0:
            x=N-data[M-1]
            y=func(x)
            X=data[0]
            Y=func(X)
            ans=ans*y*Y
            print(ans%(10**9+7))
    elif M==1:
        x=N-data[M-1]
        y=func(x)
        X=data[0]
        Y=func(X)
        ans=ans*y*Y
        print(ans%(10**9+7))
    else:
        print(func(N+1))

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
M=int(r[1])
data_pre=[input() for i in range(M)]
data=[int(s) for s in data_pre]
def func(num):
    if num<=2:
        return 1
    else:
        return int((((1+5**(1/2))/2)**num-((1-5**(1/2))/2)**num)/(5**(1/2)))
if N%2==0 and M>int(N/2):
    print(0)
elif N%2==1 and M>int((N+1)/2):
    print(0)
else:
    ans=1
    mark=0
    if M>=2:
        for i in range(1,M):
            if data[i]-data[i-1]==1:
                ans=0
                mark+=1
                print(ans)
                break
            else:
                x=data[i]-data[i-1]-1
                y=func(x)
                ans=ans*y
    if mark==0:
        x=N-data[M-1]
        y=func(x)
        X=data[0]
        Y=func(X)
        ans=ans*y*Y
        print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
r=input().split()
N=int(r[0])
M=int(r[1])
data_pre=[input() for i in range(M)]
data=[int(s) for s in data_pre]
def func(num):
    if num<=2:
        return 1
    else:
        return func(num-1)+func(num-2)
if N%2==0 and M>int(N/2):
    print(0)
elif N%2==1 and M>int((N+1)/2):
    print(0)
else:
    ans=1
    mark=0
    if M>=2:
        for i in range(1,M):
            if data[i]-data[i-1]==1:
                ans=0
                mark+=1
                print(ans)
                break
            else:
                x=data[i]-data[i-1]-1
                y=func(x)
                ans=ans*y
    if mark==0:
        x=N-data[M-1]
        y=func(x)
        X=data[0]
        Y=func(X)
        ans=ans*y*Y
        print(ans%(10**9+7))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
Stlist = [1]*N
for i in range(M):
    breakstair = int(input())
    Stlist[breakstair-1] = 0
Comb = [1,2]
if Stlist[0] == 0:
    Comb[0] = 0
    Comb[1] = 1
if Stlist[1] == 0:
    Comb[1] = 0
for i in range(2,N):
    Comb.append((Comb[i-1] + Comb[i-2])%(10**9+7))
    if Stlist[i] == 0:
        Comb[i] = 0
print(Comb[-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
res = 0
flag = True
#任意の数Kに対してたどり着く通り数
INF = 100000000000
stepList = [INF]*(N+1)
stepList[0] = 1
stepList[1] = 1
stepList[2] = 2
def stepF(K):
  if K == 0:
    return stepList[0]
  else:
    for i in range(1,K+1):
      if i == 1 or i == 2:
        pass
      else:
        if stepList[i]==INF:
          stepList[i]= stepList[i-2] + stepList[i-1]
    return stepList[K]
  
if M == 0:
  res = stepF(N)
  
else:
  List = []
  for i in range (M):
    List.append(int(input()))
  #任意の数aが壊れている場合
  
  for i in range(M):
    if i == 0:
      res = stepF(List[i]-1)
    else:
      if List[i] - List[i-1] == 1:
        flag = False
        break
      res = res * stepF(List[i]-List[i-1]-2)
  res = res * stepF(N-List[M-1]-1)
if flag:
  print(res%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
res = 0
#任意の数Kに対してたどり着く通り数
INF = 100000000000
stepList = [INF]*(N+1)
stepList[0] = 1
stepList[1] = 1
stepList[2] = 2
def stepF(K):
  if K == 0:
    return stepList[0]
  else:
    for i in range(1,K+1):
      if i == 1 or i == 2:
        pass
      else:
        if stepList[i]==INF:
          stepList[i]= stepList[i-2] + stepList[i-1]
    return stepList[K]
  
if M == 0:
  res = stepF(N)
  
else:
  List = []
  for i in range (M):
    List.append(int(input()))
  flag = True
  #任意の数aが壊れている場合
  
  for i in range(M):
    if i == 0:
      res = stepF(List[i]-1)
    else:
      if List[i] - List[i-1] == 1:
        flag = False
        break
      res = res * stepF(List[i]-List[i-1]-2)
  res = res * stepF(N-List[M-1]-1)

if flag:
  print(res%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
List = []
for i in range (M):
  List.append(int(input()))
#任意の数Kに対してたどり着く通り数
INF = 100000000000
stepList = [INF]*(N+1)
stepList[0] = 1
stepList[1] = 1
stepList[2] = 2
def stepF(K):
  if K == 0:
    return stepList[0]
  else:
    for i in range(1,K+1):
      if i == 1 or i == 2:
        pass
      else:
        if stepList[i]==INF:
          stepList[i]= stepList[i-2] + stepList[i-1]
    return stepList[K]
flag = True
#任意の数aが壊れている場合
res = 1
for i in range(M):
  if i == 0:
    res = stepF(List[i]-1)
  else:
    if List[i] - List[i-1] == 1:
      flag = False
      break
    res = res * stepF(List[i]-List[i-1]-2)
res = res * stepF(N-List[M-1]-1)

if flag:
  print(res%1000000007)
else:
  print(0)

Submission status: Runtime Error

Solution code:
n, m=map(int, input().split())
a=[0]*m
for i in range(m):
    a[i] = int(input())
ans = [0]*(n+1)
idx=0
if a[0]==1:
    idx+=1
    ans[1] = 0
    if n==1:
        pass
    elif m>=2 and a[1]==2:
        idx+=1
        ans[2]=0
    else:
        ans[2]=1
else:
    ans[1] = 1
    if n==1:
        pass
    elif a[0]==2:
        idx+=1
        ans[2]=0
    else:
        ans[2]=2

for k in range(3,n+1):
    if idx>=m or a[idx]!=k:
        ans[k]=ans[k-1]+ans[k-2]
        if ans[k]>=10**9+7:
            ans[k] %= 10**9+7
    else:
        ans[k]=0
        idx+=1

print(ans[n])

Submission status: Runtime Error

Solution code:
n, m=map(int, input().split())
a=[0]*m
for i in range(m):
    a[i] = int(input())
ans = [0]*(n+1)
idx=0
if a[0]==1:
    idx+=1
    ans[1] = 0
    if m>=2 and a[1]==2:
        idx+=1
        ans[2]=0
    else:
        ans[2]=1
else:
    ans[1] = 1
    if a[0]==2:
        idx+=1
        ans[2]=0
    else:
        ans[2]=2

for k in range(3,n+1):
    if idx>=m or a[idx]!=k:
        ans[k]=ans[k-1]+ans[k-2]
        if ans[k]>=10**9+7:
            ans[k] %= 10**9+7
    else:
        ans[k]=0
        idx+=1

print(ans[n])

Submission status: Runtime Error

Solution code:
n, m=map(int, input().split())
a=[0]*m
for i in range(m):
    a[i] = int(input())
ans = [0]*(n+1)
idx=0
if a[0]==1:
    idx+=1
    ans[1] = 0
    if a[1]==2:
        idx+=1
        ans[2]=0
    else:
        ans[2]=1
else:
    ans[1] = 1
    if a[0]==2:
        idx+=1
        ans[2]=0
    else:
        ans[2]=2

for k in range(3,n+1):
    if idx>=m or a[idx]!=k:
        ans[k]=ans[k-1]+ans[k-2]
        if ans[k]>=10**9+7:
            ans[k] %= 10**9+7
    else:
        ans[k]=0
        idx+=1

print(ans[n])

Submission status: Runtime Error

Solution code:
import sys
import functools
import operator

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

if m==0:
  print(sum(n))
  sys.exit()

if m==1 and n==1:
  print('0')
  sys.exit()

if m==1 and n==2:
  print('1')
  sys.exit()
  
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()

if a[0]==1:
  for i in range(1,m):
    if i==1:
      c.append(sum(a[i]-2))
    else:
      if a[i]-a[i-1]>2:
        c.append(sum(a[i]-a[i-1]-2))

else:
  for i in range(m):
    if i==0:
      c.append(sum(a[i]-1))
    else:
      if a[i]-a[i-1]>2:
        c.append(sum(a[i]-a[i-1]-2))

if n-a[-1]!=1:
  c.append(sum(n-a[-1]-1))

p=functools.reduce(operator.mul,c)

print(p%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import functools
import operator

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

if m==0:
  print(sum(n))
  sys.exit()

if m==1 and n==1:
  print('0')
  sys.exit()

if m==1 and n==2:
  print('1')
  sys.exit()
  
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()

if a[0]==1:
  for i in range(1,m):
    if i==1:
      c.append(sum(a[i]-2))
    else:
      if a[i]-a[i-1]>2:
        c.append(sum(a[i]-a[i-1]-2))

else:
  for i in range(m):
    if i==0:
      c.append(sum(a[i]-1))
    else:
      if a[i]-a[i-1]>1:
        c.append(sum(a[i]-a[i-1]-2))

if n-a[-1]!=1:
  c.append(sum(n-a[-1]-1))

p=functools.reduce(operator.mul,c)

print(p%1000000007)

Submission status: Runtime Error

Solution code:
import sys
import functools
import operator

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

def sum(x):
    if x==1:
        return x
    if x==2:
        return x
    return sum(x-1)+sum(x-2)

c=[] #1段ずつ連続して存在する階段の移動方法がそれぞれ何通りあるか

if m==0:
  print(sum(n))
  sys.exit()

if m==1 and n==1:
  print('0')
  sys.exit()

if m==1 and n==2:
  print('1')
  sys.exit()
  
for i in range(1,m):
  if a[i]-a[i-1]==1:
    print('0')
    sys.exit()

for i in range(m):
  if i==0:
    c.append(sum(a[i]-1))
  else:
    c.append(sum(a[i]-a[i-1]-2))

if n-a[-1]!=1:
  c.append(sum(n-a[-1]-1))

p=functools.reduce(operator.mul,c)

print(p%1000000007)