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: Runtime Error

Solution code:
N,M=map(int,input().split())
K=10**9+7
"""la=[]
for i in range(M):
    la.append(int(input()))"""
ldp=[0 for i in range(N)]
for i in range(M):
    a=int(input())
    ldp[a-1]=-1
if ldp[0]!=-1:
    ldp[0]=1
    #if ldp[1]!=-1:
    #    ldp[1]=1
if ldp[1]!=-1:
    ldp[1]+=1
    if ldp[0]!=-1:
        ldp[1]+=1
if N>=2:
    for i in range(2,N):
        if ldp[i]!=-1:
            if ldp[i-1]!=-1:
                ldp[i]=(ldp[i]+ldp[i-1])%K
            if ldp[i-2]!=-1:
                ldp[i]=(ldp[i]+ldp[i-2])%K
#print(ldp)
print(ldp[N-1])

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
K=10**9+7
"""la=[]
for i in range(M):
    la.append(int(input()))"""
ldp=[0 for i in range(N)]
for i in range(M):
    a=int(input())
    ldp[a-1]=-1
if ldp[0]!=-1:
    ldp[0]=1
    #if ldp[1]!=-1:
    #    ldp[1]=1
if ldp[1]!=-1:
    ldp[1]+=1
    if ldp[0]!=-1:
        ldp[1]+=1
for i in range(2,N):
    if ldp[i]!=-1:
        if ldp[i-1]!=-1:
            ldp[i]=(ldp[i]+ldp[i-1])%K
        if ldp[i-2]!=-1:
            ldp[i]=(ldp[i]+ldp[i-2])%K
#print(ldp)
print(ldp[N-1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M)]
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if a.count(i) >= 1:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
print(ans[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M+100)]
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if i in a:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
print(ans[N])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    exit()

a = [int(input()) for i in range(M)]
ans = [0] * (N+1)
ans[0] = 1
if a[0] != 1:   ans[1] = 1
else:   pass
for i in range(2, N+1):
    if i in a:
        ans[i] = 0
    else:
        ans[i] = (ans[i-1] + ans[i-2]) % (10**9+7)
print(ans[N])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
def input() -> str:
    return sys.stdin.readline().rstrip()
mod = 10**9 + 7
@lru_cache(maxsize=None)
def dp(i):
    if i == n - 1:
        return 1
    if i == n - 2:
        return 2 - int(n - 1 in a)
    return dp(i + 1) * int(i + 1 not in a) % mod + dp(i + 2) * int(i + 2 not in a) % mod
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
print(dp(0))

Submission status: Runtime Error

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

data=[0 for i in range(N)]
if 1 not in A:
    data[0]=1
if 2 not in A:
    data[1]=1+data[0]


for i in range(2,N):
    if i+1 not in A:
        data[i]=data[i-1]+data[i-2]
        data[i]%=mod

#print(data)

print(data[-1])

Submission status: Runtime Error

Solution code:
def main():
    N, M = list(map(int, input().split(' ')))
    hole_indice = [int(input()) - 1 for i in range(M)]
    holes = [True if i in hole_indice else False for i in range(N)]

    if holes[0] and holes[1]:
        print(0)
        return

    dp = [-1 for i in range(N)]
    dp[0] = 1
    if not holes[0]:
        dp[1] = 2
    else:
        dp[1] = 1

    for i in range(2, N):
        if holes[i]:
            if holes[i-1]:
                print(0)
                return
            else:
                dp[i] = dp[i-1]

        else:
            if not holes[i-1] and not holes[i-2]:
                dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
            else:
                dp[i] = dp[i-1]

    print(dp[N-1])

main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
array = []
c = 0
for i in range(M):
    a = int(input())
    if a-1 not in array:
        array.append(a)
    else:
        c = 1
        break
if c == 1:
    print(0)
else:
    dp = [0 for i in range(N+1)]
    dp[0] = 1
    for i in range(N-1):
        if i+1 not in array:
            dp[i+1] += dp[i]%(10**9+7)
        if i+2 not in array:
            dp[i+2] += dp[i]%(10**9+7)
if N-1 not in array:
    dp[N] += dp[N-1]%(10**9+7)
print(dp[-1]%(10**9+7))

Submission status: Runtime Error

Solution code:
import numpy as np
MOD = 1000000007
def F(n):
  if n < 0:
    return 0
  root = np.sqrt(5)
  return int(1/root * (((1+root)/2)**n - ((1-root)/2)**n))

n,m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
a = [i-2 for i in a]
a = list(map(F, a))
print(np.prod(a))

Submission status: Runtime Error

Solution code:
import numpy as np
MOD = 1000000007
def F(n):
  if n < 0:
    return 0
  root = np.sqrt(5)
  return int(1/root * (((1+root)/2)**n - ((1-root)/2)**n))

n,m = map(int, input().split())
a = [-1] + [int(input()) for i in range(m)] + [n+1]
a = [i-2 for i in a]
a = list(map(F, a))
print(a)
print(np.prod(a))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def fib(n):
  if n==1:
    return 1
  elif n<=0:
    return 0
  tmp1,tmp2=1,2
  for _ in range(n-2):
    tmp1,tmp2=tmp2,tmp1+tmp2
  return tmp2

for i in range(m):
  if i==0 and a[0]==1:
    pass
  if i==0 and a[0]!=1:
    ans*=a[i]-1
  elif i>0:
  	ans*=fib(a[i]-a[i-1]-2)
  ans%=1000000007

ans*=fib(n-a[-1]-1)
ans%=1000000007
print(ans)

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
if(n<3):
    for 
dp=[100000]*(n+1)
dp[0]=0
dp[1]=1
dp[2]=2
for i in range(m):
    a=int(input())
    dp[a]=0
for i in range(3,n+1):
    if(dp[i]==0):
        continue
    dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[n])

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
dp=[100000]*(n+1)
dp[0]=0
dp[1]=1
dp[2]=2
for i in range(m):
    a=int(input())
    dp[a]=0
for i in range(3,n+1):
    if(dp[i]==0):
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
dp=[100000]*(n+1)
dp[0]=0
dp[1]=1
dp[2]=2
for i in range(m):
    a=int(input())
    dp[a]=0
for i in range(3,n+1):
    if(dp[i]==0):
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

Submission status: Runtime Error

Solution code:
def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
if a:
  cnt=fib_memo(a[0]+1)*fib_memo(n-a[m-1]+1)
  for i in range(1,m):
    cnt*=fib_memo(a[i]-a[i-1])
  print(cnt%(10**9+7))
else:
  print(fib_memo(n+1))

Submission status: Runtime Error

Solution code:
def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
cnt=fib_memo(a[0]+1)*fib_memo(n-a[m-1]+1)
for i in range(1,m):
  cnt*=fib_memo(a[i]-a[i-1])
print(cnt%(10**9+7))

Submission status: Runtime Error

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

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

for i in range(n):
    if i == 0:
        mat[i] = 1
    if mat[i] == -1:
        continue
    if i + 1 < n+1:
        if mat[i+1] != -1:
            mat[i+1] += mat[i]
    if i + 2 < n+1:
        if mat[i+2] != -1:
            mat[i+2] += mat[i]
if mat[-1] => 0:
    print(mat[-1]%1000000007)
else:
    print(0)

Submission status: Runtime Error

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

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

for i in range(n):
    if i == 0:
        mat[i] = 1
    if mat[i] == -1:
        continue
    if i + 1 < n+1:
        if mat[i+1] != -1:
            mat[i+1] += mat[i]
    if i + 2 < n+1:
        if mat[i+2] != -1:
            mat[i+2] += mat[i]
    print(mat)
if mat[-1] => 0:
    print(mat[-1]%1000000007)
else:
    print(0)

Submission status: Runtime Error

Solution code:
def fib_memo(n):
    memo=["EMPTY"]*(n+1)
    def _fib(n):
        if n == 1:
            return 0
        elif n == 2:
            return 1
        elif memo[n] != "EMPTY":
            return memo[n]
        else:
            memo[n] = _fib(n-1)+_fib(n-2)
            return memo[n]
    return _fib(n)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
cnt=fib_memo(a[0]-1)*fib_memo(n-a[m-1]-1)
for i in range(1,m-1):
  cnt*=fib_memo(a[i]-a[i-1]-1)
print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
ans=[10*9]*n
if a[0]==1:
    ans[0]=0
else:
    ans[0]=1
if len(ans)>1:
    ans[1]=ans[0]+1
for i in range(m):
    ans[a[i]-1]=0
for j in range(n-2):
    if ans[j+2]==0:
        continue
    else:
        ans[j+2]=ans[j+1]+ans[j]
        ans[j+2]=ans[j+2]%(1000000007)
    #print(ans)
print(ans[n-1])
#print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
fib=[0,0,1,2]
for i in range(4,100005):
  fib.append(fib[i-1]+fib[i-2])

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

a.insert(0,0)
a.append(n)
ans=1
for i in range(m+1):
  ans*=fib[a[i+1]-a[i]]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
ans = [0 for _ in range(N+1)]
ans[0] = 0
if 1 not in A:
  ans[1] = 1
if 2 not in A:
  ans[2] = ans[1] + 1

for i in range(3, N+1):
  if i in A:
    ans[i] = 0
    continue
  for j in (1, 2):
    if ans[i-j] != 0:
      ans[i] += ans[i-j]
  else:
    ans[i] %= (10 ** 9 + 7)
print(ans[-1] % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
ans = [0 for _ in range(N+1)]
ans[0] = 0
if 1 not in A:
  ans[1] = 1
if 2 not in A:
  ans[2] = ans[1] + 1

for i in range(3, N+1):
  if i in A:
    ans[i] = 0
    continue
  for j in (1, 2):
    if ans[i-j] != 0:
      ans[i] += ans[i-j]

print(ans[:])

Submission status: Runtime Error

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

n, m = map(int, input().split())
a = [int(input()) - 1 for _ in range(m)]
a.append(n)

dp = [-1] * max(3, n)
dp[0] = 1
dp[1] = 1
dp[2] = 2
def stepsum(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = stepsum(n-1) + stepsum(n-2)
    return dp[n]
prev = 0
ans = 1
for ai in a:
    if prev != 0 and ai - prev < 0:
        ans = 0
        break
    ans *= stepsum(ai - prev)
    prev = ai + 2

print(ans % ( 10 ** 9 + 7 ))

Submission status: Runtime Error

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

n, m = map(int, input().split())
a = [int(input()) - 1 for _ in range(m)]
a.append(n)

dp = [-1] * n
dp[0] = 1
dp[1] = 1
dp[2] = 2
def stepsum(n):
    if dp[n] != -1:
        return dp[n]
    dp[n] = stepsum(n-1) + stepsum(n-2)
    return dp[n]
prev = 0
ans = 1
for ai in a:
    if prev != 0 and ai - prev < 0:
        ans = 0
        break
    ans *= stepsum(ai - prev)
    prev = ai + 2

print(ans % ( 10 ** 9 + 7 ))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#c dp version
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()) )
from collections import deque
a=deque(a)
mod=10**9 + 7

dp=[0]*(n+2)
dp[0]=0
dp[1]=1
aa=a.popleft()
for i in range(2,n+2):
    if i-1 == aa:
        dp[i]=0
        if len(a)>0:
            aa=a.popleft()
    else:
        dp[i]=( dp[i-1]+dp[i-2] )%mod
print(dp[-1])

Submission status: Runtime Error

Solution code:
# DP
N, M = map(int, input().split())
broken = set(map(int, input().split()))

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

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

print(dp[0])

Submission status: Runtime Error

Solution code:
# DP
N, M = map(int, input().split())
broken = list(map(int, input().split()))

MOD = 10**9+7
dp = [0 for i in range(N+1)]
dp[N] = 1

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

print(dp[0])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    a=[]
    for i in range(m):
        a.append(int(input()) )
    mod=10**9 + 7
    

    def cmb(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result

    
    c=0
    for i in range(m-1):
        if a[i]==a[i+1]-1: c+=1
    if c!=0:
        print(0)
    elif m==0:
         print( sum( cmb(n-i,i)%mod for i in range(n//2+1) )%mod )
        
        
    else:
        b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
        cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]
    
        ans=1
        for ccc in cc:
            ans = ans*ccc%mod
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#c
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()) )
mod=10**9 + 7

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (m//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
    cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

    ans=1
    for ccc in cc:
        ans = ans*ccc%mod
    print(ans)

Submission status: Runtime Error

Solution code:
#c
import sys
sys.setrecursionlimit(10000)
n,m = map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()) )
mod=10**9 + 7

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (mod//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
    cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

    ans=1
    for ccc in cc:
        ans = ans*ccc%mod
    print(ans)

Submission status: Runtime Error

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

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (mod//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
    cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

    ans=1
    for ccc in cc:
        ans = ans*ccc%mod
    print(ans)

Submission status: Runtime Error

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

def cmb(n, r, m,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % m

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % m )
        inverse.append( ( -inverse[m % i] * (mod//i) ) % m )
        g2.append( (g2[-1] * inverse[-1]) % m )
    return cmb(n,r,m,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
cc=[ sum( nCrMOD(bb-i,i,mod) for i in range(bb//2+1) )%mod for bb in b ]

ans=1
for ccc in cc:
    ans = ans*ccc%mod
print(ans)

Submission status: Runtime Error

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

def cmb(n, r, mod,g1,g2):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def nCrMOD(n,r,m):
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    for i in range( 2, n + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    return cmb(n,r,mod,g1,g2)


c=0
for i in range(m-1):
    if a[i]==a[i+1]-1: c+=1
if c!=0:
    print(0)
else:
    b=[a[0]-1] + [a[j+1]-a[j]-2 for j in range(m-1)] + [n-a[-1]-1]
cc=[ sum( nCrMOD(bb-i,i,mod) for i in range((bb)//2+1) )%mod for bb in b ]

ans=1
for ccc in cc:
    ans = ans*ccc%mod
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp_l = [1, 1]+[-1]*(n-1)

def dp(n):
  if n in A:
    dp_l[n] = 0
  
  if dp_l[n] == -1:
    dp_l[n] = (dp(n-1)+dp(n-2))%mod
  
  return(dp_l[n])

print(dp(n))

Submission status: Runtime Error

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

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

def dp(n):
  if n in A:
    return(0)
  
  if n==0:
    return(1)
  elif n==1:
    return(1)
  
  if dp_l[n] == -1:
    dp_l[n] = (dp(n-1)+dp(n-2))%mod
    return(dp_l[n])
  else:
    return(dp_l[n])
    
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]=0
if 1 in a:
  dp[1]=0
  dp[2]=1
else:
  dp[1]=1
  dp[2]=2
for i in range(3,n+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

Submission status: Runtime Error

Solution code:
memo = {}

def starsFib(n,a):
    if n == 1:
        return 1
    elif n == 2:
        return 2

    elif n in a:
        return 0
    else:
        memo[n] = starsFib(n-1,a) + starsFib(n-2,a)
        return memo[n]

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

    all = starsFib(n,a)

    ans = all % 1000000007

    print(ans)

if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque, Counter
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
ans = 1

[n,m] = inpl()
fibsec = [0]*n
fibsec[0] = 1
fibsec[1] = 1
fibsec[-1] = 0
for i in range(2,n-1):
    fibsec[i] = fibsec[i-1]+fibsec[i-2]

firsta = -1
for k in range(m):
    seconda = inp()
    ans = ans*(fibsec[seconda-firsta -2 ])%mod
    firsta = seconda

ans = ans*(fibsec[n-firsta-1])%mod
    
print(ans)

Submission status: Runtime Error

Solution code:
INF = float("inf") #const

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

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

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()
    w = sc.intarr()
    is_safe = [True] * (n+2)
    for a in w:
        is_safe[a + 1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0

    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()

Submission status: Runtime Error

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


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()[0]
    w = sc.intarr()
    is_safe = [True] * (n+2)
    for a in w:
        is_safe[a + 1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0

    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math

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


factorial_list = [1] * ((N+1)//2)
for i in range(1,((N+1)//2)):
    factorial_list[i] = factorial_list[i-1] * i

def combinations_count(n, r):
    return factorial_list[n] // (factorial_list[n - r] * factorial_list[r])


'''
def nCk(n, k):
    ret = 1
    mo = 10**9 + 7
    for i in range(k):
        ret = ret * (n - i) * pow(i + 1, mo - 2, mo) % mo
    return ret
'''

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += combinations_count(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
max_diff = -1
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)


all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
print(all_sum%(10**9+7))

Submission status: Runtime Error

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

def recur(step):
  if step == N:
    return 1
  
  elif step in A or step > N:
    return 0
  
  else:
    ret1 = recur(step + 1) 
    ret2 = recur(step + 2) 
    return (ret1 + ret2) % (10 ** 9 + 7) 
    
print(recur(0))

Submission status: Runtime Error

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

def recur(step):
  if step == N:
    return 1　
  
  elif step in A or step > N:
    return 0
  
  else:
    ret1 = recur(step + 1) 
    ret2 = recur(step + 2) 
    return (ret1 + ret2) % (10 ** 9 + 7) 
    
print(recur(0))

Submission status: Runtime Error

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

def recur(step):
  if step == N:
    return 1　
  
  elif step in A or step > N:
    return 0
  
  else:
    ret1 = recur(step + 1) 
    ret2 = recur(step + 2) 
    return (ret1 + ret2) / (10 ** 9 + 7) 
    
print(recur(0))

Submission status: Runtime Error

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

def recur(step):
  if step == N:
    return 1
  
  elif step in A or step > N:
    return 0
  
  else:
    ret1 = recur(step + 1) 
    ret2 = recur(step + 2) 
    return ret1 + ret2
    
print(recur(0) % (10 ** 9 + 7) )

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
dp=[0]*n
dp[0]=0
dp[1]=1
for j in range(2,n):
    dp[j]=dp[j-1]+1+dp[j-2]+1
print(dp[n-2*m]+m)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input())
a=[int(input()) for i in range(m)]
dp=[0]*n
dp[0]=0
dp[1]=1
for j in range(2,n):
    dp[j]=dp[j-1]+1+dp[j-2]+1
print(dp[n-2*m])

Submission status: Runtime Error

Solution code:
n,m=map(int,input())
a=int(input())
dp=[0]*n
dp[0]=0
dp[1]=1
for j in range(2,n):
    dp[j]=dp[j-1]+1+dp[j-2]+1
print(dp[n-2*m])

Submission status: Runtime Error

Solution code:
n,m=map(int,input())
a=list(int(input()))
dp=[0]*n
dp[0]=0
dp[1]=1
for j in range(2,n):
    dp[j]=dp[j-1]+1+dp[j-2]+1
print(dp[n-2*m])

Submission status: Runtime Error

Solution code:
n,m=map(int,input())
a=list(int(input()) for i in range(m))
dp=[0]*n
dp[0]=0
dp[1]=1
for j in range(2,n):
    dp[j]=dp[j-1]+1+dp[j-2]+1
print(dp[n-2*m])

Submission status: Runtime Error

Solution code:
n,m=map(int,input())
a=list(int(input()) for i in range(m))
dp=[0]*n
dp[0]=0
dp[1]=1
for j in range(2,n):
    dp[j]=dp[j-1]+1+dp[j-2]+1
print(dp[n-2m])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

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

k = ((a[0]-1) - 0) - 1
tmp = 1 # noskip
for i in range(k//2+1):
    #print(i)
    tmp += k - 2*i
way.append(tmp)

for i in range(1, M):
    if a[i] - a[i-1] == 1:
        print(0)
        exit()
    else:
        k = ((a[i]-1) - (a[i-1]+1)) - 1
        tmp = 1 # noskip
        for i in range(k//2+1):
            tmp += k - 2*i
        way.append(tmp)

k = (N - (a[M-1]+1)) - 1
tmp = 1 # noskip
for i in range(k//2+1):
    tmp += k - 2*i
way.append(tmp)

#print(way)
res = 1
for i in range(M+1):
    res *= way[i]
res = res % 1000000007
print(res)