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:
a = [0]

N, M = map(int, input().split(' '))

for _ in range(M):
    a.append(int(input()))
a.append(N+1)

#print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

#print(b)

def func(n):
    if n == -2:
        retval = 0
    elif n == -1:
        retval = 1
    elif n == 0:
        retval = 1
    elif n == 1:
        retval = 1
    else:
        retval = func(n-2) + func(n-1)
    return retval % (10**9 + 7)

result = 1

for i in range(M+1):
    result = result * func(b[i])
    result = result % (10**9 + 7)

print(result)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
print(0)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
t=list(map(int, input().split()))
N=int(t[0])
M=int(t[1])
a=[-1]
for i in range(M):
        a.append(int(input()))
a.append(N+1)
d=1
for i in range(M+1):
        b=a[i+1]-a[i]-1
        c=0
        if (b==0):c=0
        else:
                for j in range(int((b-1)/2)+1):
                        c = c + int(comb((b-1-j),j))
                        c = c%1000000007
        d = d*c
        d = d%1000000007
print(d)

Submission status: Runtime Error

Solution code:
a = [0]

N, M = map(int, input().split(' '))

for _ in range(M):
    a.append(int(input()))
a.append(N+1)

#print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

#print(b)

def func(n):
    if n == -1:
        retval = 1
    elif n == 0:
        retval = 1
    elif n == 1:
        retval = 1
    else:
        retval = func(n-2) + func(n-1)
    return retval % (10**9 + 7)

result = 1

for i in range(M+1):
    result = result * func(b[i])
    result = result % (10**9 + 7)

print(result)

Submission status: Runtime Error

Solution code:
a = [0]

N, M = map(int, input().split(' '))

for _ in range(M):
    a.append(int(input()))
a.append(N+1)

print(a)

b = []
for i in range(M+1):
    b.append(a[i+1] - a[i] - 2)

print(b)

def func(n):
    if n == -1:
        retval = 1
    elif n == 0:
        retval = 1
    elif n == 1:
        retval = 1
    else:
        retval = func(n-2) + func(n-1)
    return retval % (10**9 + 7)

result = 1

for i in range(M+1):
    result = result * func(b[i])
    result = result % (10**9 + 7)

print(result)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
t=list(map(int, input().split()))
N=int(t[0])
M=int(t[1])
a=[-1]
for i in range(M):
        a.append(int(input()))
a.append(N+1)
print(a)
d=1
for i in range(M+1):
        b=a[i+1]-a[i]-1
        c=0
        if (b==0):c=0
        else:
                for j in range(int((b-1)/2)+1):
                        c = c + int(comb((b-1-j),j))
                        c = c%1000000007
        d = d*c
        d = d%1000000007
print(d)

Submission status: Runtime Error

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

dp = [0]*N

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

for i in range(2,N):
  dp[i] = (dp[i-1]+dp[i-2]) *a[i]
  
print(dp[-1]%mod)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    n,m=map(int,input().split())
    if n == 1:
        print(1)
        return
    aa=[]
    for _ in range(m):
        aa.append(int(input()))
    for i in range(m-1):
        if aa[i]+1==aa[i+1]:
            print(0)
            return
    cc = [0] * n
    i = 0
    j = 2 
    cc[0] = 1
    if aa[0] > 1:
        cc[1] = 1
    else:
        cc[1] = 0
        i += 1
    while j < n:
        if i < m and aa[i] == j:
            i+=1
        else:
            cc[j]=cc[j-1]+cc[j-2]
        j+=1
    print((cc[n-1]+cc[n-2])%1000000007)

main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
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 i in a:
  else:
    dp[i] = dp[i-1]+dp[i-2]
print(dp[-1] % (10**9+7))

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]
b.extend(a)
b.extend([N+1])
ans = 1
import sympy as sym
def fibo(n):

    x = sym.symbols('x',nonnegative=True,integer=True)
    Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
    result=Fib.subs(x,n)
    result=sym.simplify(result) #式の整理
    return result

for i in range(M+1):
    dan = b[i+1]-1 - b[i]
    ans = ans*fibo(dan+1)%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]
b.extend(a)
b.extend([N+1])
ans = 1
import sympy as sym
def fibo(n):
    if n < 1:
        return 0
    else:
        x = sym.symbols('x',nonnegative=True,integer=True)
        Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(n-1)-((1-sym.sqrt(5))/2)**(n-1))
        result=Fib.subs(x,n)
        result=sym.simplify(result) #式の整理
        return result

for i in range(M+1):
    dan = b[i+1]-1 - b[i]
    ans = ans*fibo(dan)%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]
b.extend(a)
b.extend([N+1])
ans = 1
def fibo(t):
    if t < 1:
        return 0
    else:
        fi = (int(1/math.sqrt(5)*(((1+math.sqrt(5))/2)**dan-((1-math.sqrt(5))/2)**dan)+0.0000001))%1000000007
        return fi
for i in range(M+1):
    dan = b[i+1]-1 - b[i]
    ans = ans*fibo(dan)%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]
b.extend(a)
b.extend([N+1])
ans = 1
def fibo(t):
    if t == 0:
        return 0
    else:
        fi = (int(1/math.sqrt(5)*(((1+math.sqrt(5))/2)**dan-((1-math.sqrt(5))/2)**dan)+0.01))%1000000007
        return fi
for i in range(M+1):
    dan = b[i+1]-1 - b[i]
    ans = ans*fibo(dan)%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [-1]
b.extend(a)
b.extend([N+1])
ans = 1
def fibo(t):
    if t == 0:
        return 0
    else:
        fi = int(1/math.sqrt(5)*(((1+math.sqrt(5))/2)**dan-((1-math.sqrt(5))/2)**dan)+0.01)
        return fi
for i in range(M+1):
    dan = b[i+1]-1 - b[i]
    ans = ans*fibo(dan)%1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = [0]
b.extend(a)
b.extend([N+1])
ans = 1
for i in range(M+1):
    dan = b[i+1] - b[i]
    tori = int(1/math.sqrt(5)*(((1+math.sqrt(5))/2)**dan-((1-math.sqrt(5))/2)**dan)+0.01)
    ans *= tori
print(ans)

Submission status: Runtime Error

Solution code:
using namespace std;
#include<iostream>
#include<vector>
int N,M;
const int DIM=100010;
long X[DIM]; 
int ans=1;
const long base=1000000007; 


long FIB(int i){
    if (X[i] != 0) {return X[i];}
    X[i] = FIB(i-2);
    X[i] = (X[i] + FIB(i-1))% base; 
    return X[i]; 
}


int main(){
    int a,i,j,k,x,y,z;
    int c = 0; 
    long s; 
    cin >> N >> M; 
    // cout << N << " " << M << "\n"; 
    for(i=0;i<DIM;i++){X[i]=0;}
    X[0]=0;
    X[1]=1; 
    X[2]=1;
    for(i=0;i<M;i++){
        cin >> a; 
        if (c == a || a >= N){ 
            cout << 0 << endl; // Exit. Serial skip 
            exit(0);
        }
        s = FIB(a-c);
        ans=(ans * s ) % base;
        // cout << a << " " << s << " " << ans << endl;
        c = a + 1;
    }
    s = FIB(N-c+1);
    ans=(ans * s ) % base;
    // cout << M << " " << s << " " << ans << endl;
    cout << ans  << endl; // Exit. Serial skip 

}

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[-1]
ans=0

for i in range(m):
    b=int(input())
    if a[i]==b-1:
        ans=1
        print(0)
    a.append(b)

a.append(n+1)



#k段を上る上り方を数える
#１段上るをi回、２段上るをj回
def cases(k):
    sum=0
    for j in range(k//2+1):
        i=k-2*j
        s=1
        if j>=1:
            for l in range(i+1,i+j+1):
                s=s*l
            for p in range(1,j+1):
                s=s/p
        sum+=int(s)
    return int(sum)

counter=1
if ans==0:
    for x in range(m+1):
        y=cases(a[x+1]-a[x]-2)
        counter=counter*y
    print(counter%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[-1]
ans=0

for i in range(m):
    b=int(input())
    if a[i]==b-1:
        ans=1
        print(0)
    a.append(b)

a.append(n+1)



#k段を上る上り方を数える
#１段上るをi回、２段上るをj回
def cases(k):
    sum=0
    for j in range(k//2+1):
        i=k-2*j
        s=1
        if j>=1:
            for l in range(i+1,i+j+1):
                s=s*l
            for p in range(1,j+1):
                s=s/p
        sum+=int(s)
    return sum

counter=1
if ans==0:
    for x in range(m+1):
        y=cases(a[x+1]-a[x]-2)
        counter=counter*y
    print(counter%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[-1]
ans=0

for i in range(m):
    b=int(input())
    if a[i]==b-1:
        ans=1
        print(0)
    a.append(b)

a.append(n+1)

print(a)

#k段を上る上り方を数える
#１段上るをi回、２段上るをj回
def cases(k):
    sum=0
    for j in range(k//2+1):
        i=k-2*j
        s=1
        if j>=1:
            for l in range(i+1,i+j+1):
                s=s*l
            for p in range(1,j+1):
                s=s/p
        sum+=int(s)
    return sum

counter=1
if ans==0:
    for x in range(m+1):
        y=cases(a[x+1]-a[x]-2)
        print(y)
        counter=counter*y
    print(counter%1000000007)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[]
for i in range(M):
  L.append(int(input()))
if L[0]-1==0:
  pass
else:
  q=(L[0]-1)//2+1
i=0
while i<M-1:
  if L[i]+1==L[i+1]:
    print(0)
    exit()
  else:
    q+=(L[i+1]-L[i]-1)//2+1
    i+=1
if L[M-1]==N-2:
  print(0)
  exit()
else:
  q+=(N-L[M-1]-1)//2+1
  print(q)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
L=[]
for i in range(M):
  L.append(int(input()))
if L[0]-1==0:
  pass
else:
  q=(L[0]-1)//2+1
i=1
while i<N-1:
  if L[i]+1==L[i+1]:
    print(0)
    exit()
  else:
    q+=(L[i+1]-L[i]-1)//2+1
    i+=1
if L[N-1]==N-2:
  print(0)
  exit()
else:
  q+=(N-L[N-1]-1)//2+1
  print(q)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] *(N+2)
    ckc = [True] * (N+2)
    for i in a:
        ckc[i] = False

    def f(n: int):
        if(dp[n] != 0):
            return dp[n]

        if n <= 0:
            dp[n] = 0
        else:
            if not ckc[n-1] and not ckc[n-2]:
                dp[n] = 0
            elif not ckc[n-1]:
                dp[n] = f(n-2) % MOD
            elif not ckc[n-2]:
                dp[n] = f(n-1) % MOD
            else:
                dp[n] = (f(n-1) + f(n-2)) % MOD
            
        return dp[n]

    dp[0] = 1
    f(N)
    print(dp[N])
    # print(dp)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] *(N+2)

    def f(n: int):
        if(dp[n] != 0):
            return dp[n]

        if n <= 0:
            dp[n] = 0
        else:
            if n-1 in a and n-2 in a:
                dp[n] = 0
            elif n-1 in a:
                dp[n] = f(n-2) % MOD
            elif n-2 in a:
                dp[n] = f(n-1) % MOD
            else:
                dp[n] = (f(n-1) + f(n-2)) % MOD
            
        return dp[n]

    dp[0] = 1
    f(N)
    print(dp[N])
    # print(dp)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
lin = [int(stdin.readline().rstrip()) for _ in range(m)]

for i in range(len(lin)-1):
    if lin[i] + 1 == lin[i+1]:
        print(0)
        exit()

dp = [-1 for _ in range(n+1)]
dp[0] = 1
if lin[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2,n+1):
    if i in lin:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Runtime Error

Solution code:
# C - Typical Stairs
N,M = map(int, input().split())
a = [int(input()) for i in range(M)]
tmp0 = 1
tmp1 = 1
#穴がある場合の場合わけ
if len(a) == 1:
    tmp = 2*3
else:
    for i in range(1,M):
        if a[i] == a[i-1]+1:
            print(0)
            exit()
        elif a[i] == 1 or a[i] == N-1:
            tmp0 *= 2
        elif a[i] == a[i-1]+2:
            tmp0 *= 2*2
        else:
            tmp1 *= 2*3
    tmp = tmp0 + tmp1

ans = int(2**(N+1-2)/(tmp))
print(ans % (10**9+7))

Submission status: Runtime Error

Solution code:
# C - Typical Stairs
N,M = map(int, input().split())
a = [int(input()) for i in range(M)]
tmp0 = 1
tmp1 = 1
#穴がある場合の場合わけ
if len(a) == 1:
    tmp = 2*3
else:
    for i in range(1,M):
        if a[i] == a[i-1]+1:
            print(0)
            exit()
        elif a[i] == 1 or a[i] == N-1:
            tmp0 *= 2
        elif a[i] == a[i-1]+2:
            tmp0 *= 2*2
        else:
            tmp1 *= 2*3
    tmp = tmp0 * tmp1

ans = int(2**(N+1-2)/(tmp))
print(ans % (10**9+7))

Submission status: Runtime Error

Solution code:
def fibonacci(N):
    a = 1
    b = 2
    c = 0

    if N <= 1:
        return 1
    elif N == 2:
        return 2
    else:
        for i in range(N-2):
            c = a+b
            a = b
            b = c
    return c


def main():
    N,M = map(int,input().split())
    A = [int(input()) for _ in range(M)]

    temp = 1
    for i in range(M+1):
        if i == 0:
            num = fibonacci(A[i]-1)
        else:
            if i <= M-1:
                if A[i-1] == A[i]-1:
                    print(0)
                    return
                num = fibonacci(A[i]-A[i-1]-2)
            else:
                num = fibonacci(N-A[i-1]-1)
        temp *= num
    print(temp%1000000007)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def fibonacci(N):
    a = 1
    b = 2
    c = 0

    if N <= 1:
        return 1
    elif N == 2:
        return 2
    else:
        for i in range(N-2):
            c = a+b
            a = b
            b = c
    return c

def main():

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

    temp = 1
    for i in range(M+1):
        if i == 0:
            num = fibonacci(A[i]-1)
        else:
            if i <= M-1:
                if A[i-1] == A[i]-1:
                    print(0)
                    return
                num = fibonacci(A[i]-A[i-1]-2)
            else:
                num = fibonacci(N-A[i-1]-1)
        temp *= num
    print(temp%1000000007)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def fibcmb(start,end):
    start += 1
    end -= 1
    up = end - start
    a1 = 1
    a2 = 2
    if up < 0:
        return 0
    elif up == 0:
        return 1
    elif up == 1:
        return a1
    elif up == 2:
        return a2
    else:
        for _ in range(up-2):
            an = a1 + a2
            a1 = a2
            a2 = an
        return an

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
ans = 1
cmb = [0]*(m+1)
cmb[0] = fibcmb(-1,a[0])
for i in range(1,m):
    cmb[i] = fibcmb(a[i-1],a[i])
cmb[-1] = fibcmb(a[-1],n+1)
for i in range(m+1):
    ans *= cmb[i]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
mod=10**9+7
d=[mod]*(n+1)
d[0]=1;d[1]=1
for i in a:
  d[a]=0
for i in range(2,n+1):
  d[i]=min(d[i],(d[i-1]+d[i-2])%mod)
print(d[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
  A.append(int(input()))
ans=0
MOD=1000000007
dp=[]
for i in range(N-1,0,-1):
  if i in A:
    dp[i]=0
    continue
  dp[i]=dp[i+1]+dp[i+2]
  
ans=dp[0]
ans/=MOD
print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    N,M = map(int, input().split())
    
    l = [-1]*(N+1)
    for m in range(M):
        a = int(input())
        l[a] = 0
    if l[1] == 0 and l[2] == 0:
        return 0
    elif l[1] == 0 and l[2] != 0:
        l[2] = 1
    elif l[1] != 0 and l[2] == 0:
        l[1] = 1
    else:
        l[1] = 1
        l[2] = 2
    
    if N == 1:
        return 1
    if N == 2:
        return 2
    
    l.pop(0)
    for i in range(2,N):
        if l[i] == 0:
            continue
        else:
            l[i] = l[i-1] + l[i-2]
    
    return l[-1]%1000000007


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

Submission status: Runtime Error

Solution code:
import sys

def solve():
    N,M = map(int, input().split())
    
    l = [-1]*(N+1)
    for m in range(M):
        a = int(input())
        l[a] = 0
    if l[1] == 0 and l[2] == 0:
        return 0
    elif l[1] == 0 and l[2] != 0:
        l[2] = 1
    elif l[1] != 0 and l[2] == 0:
        l[1] = 1
    else:
        l[1] = 1
        l[2] = 2
    
    if N == 1:
        return 1
    if N == 2:
        return 2
    
    l.pop(0)
    for i in range(2,N):
        if l[i] == 0:
            continue
        else:
            l[i] = l[i-1] + l[i-2]
    
    return l[-1]%1000000007


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

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
stairs_exist = np.ones(N+1)

for c in range(M):
    stairs_exist[int(input())] = 0
    
steps = np.zeros(N+1)
steps[0] = 1
for i in range(N):
    for j in range(i+1, min(N+1, i+3)):
        if stairs_exist[j]:
            steps[j] += steps[i]
            
print(int(steps[-1] % (10 ** 9 + 7)))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
stairs_exist = np.ones(N+1)

for c in range(M):
    stairs_exist[int(input())] = 0
    
steps = np.zeros(N+1)
steps[0] = 1
for i in range(N):
    for j in range(i+1, min(N+1, i+3)):
        if stairs_exist[j]:
            steps[j] += steps[i]
            
print(int(steps[-1]))

Submission status: Runtime Error

Solution code:

N, M = map(int, input().split())
mod = 10**9 + 7
a = [int(input()) for _ in range(M)]

b = [0] * N

a = [0] + a
if N == 1:
    print(1)
    quit()
elif M == 0:
    ans = b[N]
    print(ans)
    quit()
else:
    ans = b[a[1] - a[0] -1]

b[0] = 1
b[1] = 2
for i in range(2, N):
    b[i] = b[i-1] + b[i-2]
b = [1] + b


for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        quit()


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

ans *= b[N - a[M] -1]
print(ans % mod)

Submission status: Runtime Error

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

b = [0] * N

a = [0] + a
if M == 0:
    ans = b[N]
    print(ans)
    quit()
elif N == 1:
    print(1)
    quit()
else:
    ans = b[a[1] - a[0] -1]

b[0] = 1
b[1] = 2
for i in range(2, N):
    b[i] = b[i-1] + b[i-2]
b = [1] + b


for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        quit()


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

ans *= b[N - a[M] -1]
print(ans % mod)

Submission status: Runtime Error

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

b = [0] * N

a = [0] + a
if M == 0:
    ans = b[N]
    print(ans)
    quit()
else:
    ans = b[a[1] - a[0] -1]

b[0] = 1
b[1] = 2
for i in range(2, N):
    b[i] = b[i-1] + b[i-2]
b = [1] + b


for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        quit()


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

ans *= b[N - a[M] -1]
print(ans % mod)

Submission status: Runtime Error

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

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


for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        quit()


a = [0] + a
if M == 0:
    ans = b[N]
    print(ans)
    quit()
else:
    ans = b[a[1] - a[0] -1]
for i in range(2, M+1):
    ans *= b[a[i]-1 - a[i-1]- 1]

ans *= b[N - a[M] -1]
print(ans % mod)

Submission status: Runtime Error

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

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


for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        quit()


a = [0] + a
ans = b[a[1] - a[0] -1]
for i in range(2, M+1):
    ans *= b[a[i]-1 - a[i-1]- 1]

ans *= b[N - a[M] -1]
print(ans % mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(100000)

memo  =[-1]*(N+2)
memo[0] = 1
memo[1] = 1
def stair_count(n):
    for j in range(2,n+1):
        memo[j] = memo[j-1] + memo[j-2]

start = 0
answer = 1
dif = []
for i in a:
    if i == start:
        print(0)
        exit()
    else:
        n = i-1-start
        dif.append(n)
        start = i+1
stair_count(max(dif))
for i in a:
        answer = (answer * memo[n])

n = N -start
answer = answer * memo[n]
print(answer%1000000007)

Submission status: Runtime Error

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

memo  =[-1]*(N+2)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)

Submission status: Runtime Error

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

memo  =[-1]*(N+1)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)

Submission status: Runtime Error

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

memo  =[-1]*N
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)

Submission status: Runtime Error

Solution code:
n = list(map(int, input().split()))
s = [int(input()) for i in range(n[1])]
s.append(n[0]+1)
memo = [0] * 100000
def stairs(x):
    memo[0] = 1
    memo[1] = 1
    for i in range(2, x+1):
        memo[i] = memo[i-2] + memo[i-1]

salst = [s[0]-1]
for i in range(n[1]):
    sa = (s[i+1]-1) - (s[i]+1)
    salst.append(sa)
    if sa < 0:
        break
if salst[-1] < 0:
    print(0)
else:
    ans = 1
    maxnum = max(salst)
    stairs(maxnum)
    for l in salst:
        ans *= memo[l]
    print(ans%1000000007)

Submission status: Runtime Error

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

memo  =[0]*1000000
def stair_count(n):
    if memo[n]!= 0:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
    #print("i={}".format(i))
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
    #print("answer={}".format(answer))
print(answer%1000000007)

Submission status: Runtime Error

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

def stairs(x):
    if x > 2:
        return stairs(x-1) + stairs(x-2)
    elif x == 2:
        return 2
    elif x == 1 or x == 0:
        return 1

salst = [s[0]-1]
for i in range(n[1]):
    sa = (s[i+1]-1) - (s[i]+1)
    salst.append(sa)
    if sa < 0:
        break
if salst[-1] < 0:
    print(0)
else:
    ans = 1
    for k in range(len(salst)):
        ans *= stairs(salst[k])

    print(ans%1000000007)

Submission status: Runtime Error

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

def stairs(x):
    if x > 2:
        return stairs(x-1) + stairs(x-2)
    elif x == 2:
        return 2
    elif x == 1 or x == 0:
        return 1

sa = [s[0]-1]
for i in range(n[1]):
    sa.append((s[i+1]-1) - (s[i]+1))
ans = 1
for k in range(len(sa)):
    ans *= stairs(sa[k])

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math
def calc_pattern(stairs):
    if stairs<=3:
        return stairs
    d=stairs//2+1
    l=[(math.factorial(i+(stairs-i*2))/math.factorial(i)/math.factorial(stairs-i*2))%1000000007  for i in range(d)]
    return int((sum(l))%1000000007)

N,M=map(int,input().split())
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
s=1
for m in range(M+1):
    if A[m+1]==1 or A[m]==N-1:
        continue
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
        s*=calc_pattern(A[m+1]-1 - (A[m]+1))
        s%=1000000007
print(int(s))

Submission status: Runtime Error

Solution code:
import math
def calc_pattern(stairs):
    if stairs<=3:
        return stairs
    d=stairs//2+1
    l=[(math.factorial(i+(stairs-i*2))/math.factorial(i)/math.factorial(stairs-i*2))%1000000007  for i in range(d)]
    return (sum(l))%1000000007

N,M=map(int,input().split())
A=[-1]
A.extend([int(input()) for m in range(M)])
A.append(N+1)
s=1
for m in range(M+1):
    if A[m+1]==1 or A[m]==N-1:
        continue
    if A[m]+1==A[m+1]:
        print(0)
        exit()
    else:
        s*=calc_pattern(A[m+1]-1 - (A[m]+1))
        s%=1000000007
print(int(s))