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: Time Limit Exceeded

Solution code:
import sys

def main():
    N, M = map(int, input().split())
    a = [int(sys.stdin.readline().strip()) for _ in range(M)]

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

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N, M = map(int, input().split())

    a=[0] * M
    for x in range(M):
        a[x] = int(sys.stdin.readline().strip())

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

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N, M = map(int, input().split())
    a = [int(sys.stdin.readline().strip()) for _ in range(M)]

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

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    N, M = map(int, input().split())
    a = [int(sys.stdin.readline().strip()) for _ in range(M)]

    dp = [0]*(N+1)

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

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    dp = [0]*(N+1)

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

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

main()

Submission status: Time Limit Exceeded

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

def main():
    MOD = 1000000007
    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    dp = [0] * (n+1)
    dp[:2] = 1, 1 if 1 not in a else 0

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    MOD = 1000000007
    n, m = map(int, input().split())

    a = []
    pre = -10
    for _ in range(m):
        i = int(input())
        if i == pre + 1:
            print(0)
            quit()
        a.append(i)
        pre = i

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1#0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    A = int(input())
    a.append(A)
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1#0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    A = int(input())
    a.append(A)
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1#0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input()) for x in range(m)]
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1 #0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) 
N, M = map(int, input().split())
a_list = []
dp = [0]*(N+1)
for _ in range(M):
  a = int(input())
  a_list.append(a)

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#n段の上り方のバリエーションはフィボナッチ数列になっている

N, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if i in alist:
        li[i] = 0
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = ((li[i-1] + li[i-2])%(10**9+7))
print(li[N]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
alist = list()
for _ in range(M):
    alist.append(int(input()))


li = {}
li[0] = 1

for i in range(1,N+1):
    if i in alist:
        li[i] = 0
    else:
        if i == 1:
            li[i] = 1
        else:
            li[i] = li[i-1] + li[i-2]
print(li[N]%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n, m = map(int, input().split())
stairs = [0]*(n+1)
broken = []
stairs[0] = 1

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

for i in range(n+1):
    if i in broken:
        continue
    if i >= 2:
        stairs[i] = stairs[i-1] + stairs[i-2]
    elif i == 1:
        stairs[i] = stairs[i-1]

print(stairs[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n, m = map(int, input().split())
stairs = [0]*(n+1)
broken = []
stairs[0] = 1

for i in range(m):
    broken.append(int(input()))

for i in range(n+1):
    if i in broken:
        continue
    if i >= 2:
        stairs[i] = stairs[i-1] + stairs[i-2]
    elif i == 1:
        stairs[i] = stairs[i-1]

print(stairs[-1]%mod)

Submission status: Time Limit Exceeded

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

MOD = 1000000007


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

    for now in range(n):
        for next_ in range(now + 1, min(now + 2, n) + 1):
            if next_ not in a:
                steps[next_] += steps[now]
                steps[next_] %= MOD
    print(steps[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 1000000007

n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
steps = [0] * (n + 1)
steps[0] = 1

for now in range(n):
    for next_ in range(now + 1, min(now + 2, n) + 1):
        if next_ not in a:
            steps[next_] += steps[now]
            steps[next_] %= MOD
print(steps[-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
steps = [0] * (n + 1)
steps[0] = 1

for now in range(n):
    for next_ in range(now + 1, min(now + 2, n) + 1):
        if next_ not in a:
            steps[next_] += steps[now]
            steps[next_] %= MOD
print(steps[-1])

Submission status: Time Limit Exceeded

Solution code:
import math

def perm(n, r):
    return math.factorial(n) // math.factorial(n - r)

def comb(n, r):
    return perm(n, r) // math.factorial(r)


n, m = map(int, input().split())

A = [int(input()) for _ in range(m)]
for i in range(m - 1):
    if A[i + 1] - A[i] == 1:
        ans = 0
        print(ans)
        exit()

S = []
for a in A:
    S.extend((a - 1, a, a + 1))
S.insert(0, 0)
S.append(n)

ans = 1
for i in range(len(S) - 1):
    r = S[i + 1] - S[i]
    if r > 1:
        c = 0
        t_max = r // 2
        for t in range(t_max + 1):
            c += comb(r - t, t)
        ans *= c

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

Submission status: Time Limit Exceeded

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

ways=[]
nextbreak = -1
try:
    nextbreak=a[0]
except IndexError:
    nextbreak=-1
    
for i in range(N+1):
    if i==nextbreak:
        a = a[1:]
        try:
            nextbreak=a[0]
        except IndexError:
            nextbreak=0
        ways+=[0]
    elif i==0:
        ways +=[1]
    elif i==1:
        ways +=[1]
    else:
        ways+=[(ways[i-2]+ways[i-1])%1000000007]
    if ways[-1]==0 and ways[-2]==0:
        break
        
print(ways[-1])

Submission status: Time Limit Exceeded

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

ways=[]
nextbreak = -1
try:
    nextbreak=a[0]
except IndexError:
    nextbreak=-1
    
for i in range(N+1):
    if i==nextbreak:
        a = a[1:]
        try:
            nextbreak=a[0]
        except IndexError:
            nextbreak=0
        ways+=[0]
    elif i==0:
        ways +=[1]
    elif i==1:
        ways +=[1]
    else:
        ways+=[(ways[i-2]+ways[i-1])%1000000007]
print(ways[-1])

Submission status: Time Limit Exceeded

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

ways=[]
for i in range(N+1):
    if i in a:
        a=a[1:]
        ways+=[0]
    elif i==0:
        ways +=[1]
    elif i==1:
        ways +=[1]
    else:
        ways+=[(ways[i-2]+ways[i-1])%1000000007]
print(ways[-1])

Submission status: Time Limit Exceeded

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

ways=[]
for i in range(N+1):
    if i in a:
        ways+=[0]
    elif i==0:
        ways +=[1]
    elif i==1:
        ways +=[1]
    else:
        ways+=[(ways[i-2]+ways[i-1])%1000000007]
print(ways[-1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(m):
    a.append(int(input()))

if 1 in a and 2 in a:
    dp.append(0)
    dp.append(0)
    print(0)
    exit()
elif 1 in a and 2 not in a:
    dp.append(0)
    dp.append(1)
elif 1 not in a and 2 in a:
    dp.append(1)
    dp.append(0)
else:
    dp.append(1)
    dp.append(2)

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

print(dp[n])

Submission status: Time Limit Exceeded

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

for i in range(m):
    a.append(int(input()))

if 1 in a and 2 in a:
    dp.append(0)
    dp.append(0)
elif 1 in a and 2 not in a:
    dp.append(0)
    dp.append(1)
elif 1 not in a and 2 in a:
    dp.append(1)
    dp.append(0)
else:
    dp.append(1)
    dp.append(2)

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

print(dp[n])

Submission status: Time Limit Exceeded

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

for i in range(1, n+1):
    if i in stairs: 
        dp[i] = 0
        continue

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

print(dp[n])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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 in a):
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
dp[0] = 1
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
dp[0] = 1
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1

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

print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0] * (n+1)
dp[0] = 1
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1
for i in range(2,N+1):
  if (i-2 in a) and (i-1 in a):
    dp[-1] = 0
    break
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a:
    dp[i] = dp[i-2]
  else:
    dp[i] = dp[i-1] + dp[i-2]

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
a = [int(input()) for i in range(M)]
dp = [0 for i in range(N+1)]
dp[0] = 1
dp[1] = 1
i = 2
while i <= N:
  if (i-2 in a) and (i-1 in a):
    dp[-1] = 0
    break
  elif i-2 in a:
    dp[i] = dp[i-1]
  elif i-1 in a:
    dp[i] = dp[i-2]
  else:
    dp[i] = dp[i-1] + dp[i-2]
  i+=1

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

Submission status: Time Limit Exceeded

Solution code:
# Typical Stairs
import sys
input = sys.stdin.readline
import numpy as np

def main():
    n, m = map(int, input().split())
    a = []
    a_ = a.append
    MOD = 10**9 + 7
    for i in range(m):
        a_(int(input()))

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

    a = np.array(a)

    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    dp = np.array(dp)
    if 1 in a:
        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]) % MOD

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Typical Stairs
import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = []
    a_ = a.append
    MOD = 10**9 + 7
    for i in range(m):
        a_(int(input()))

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

    dp = [0 for i in range(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:
            dp[i] = 0
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Typical Stairs

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

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

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:
        dp[i] = 0
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
A = tuple([int(input()) for _ in range(M)])
MOD = 1000000007

dp = np.zeros(N + 2, dtype='int')
dp[0] = 1
for now in range(N):
    for _next in range(now + 1, now + 3):
        if _next not in A:
            dp[_next] += dp[now]
            dp[_next] %= MOD
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.array([int(input()) for _ in range(M)])
MOD = 1000000007

dp = np.zeros(N + 2, dtype='int')
dp[0] = 1
for now in range(N):
    for _next in range(now + 1, now + 3):
        if _next not in A:
            dp[_next] += dp[now]
            dp[_next] %= MOD
print(dp[N])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

dp = [0]*(N+1)
if N == 1:
    if 1 in A:
        print('0')
        sys.exit()
    else:
        print('1')
        sys.exit()

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

print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7  # prime number
 
def cmb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod

N,M = map(int,input().split())
ans = 1
broken = [-1]
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
dp = [0]*(N+1)
dp[0]= 1
dp[1]= 1
for k in range(1,N+1):
  if k == 1:
    if k in broken:
      dp[k] = 0
    else:
      dp[1] = 1
  else:
    if k in broken:
      dp[k] = 0
    else:
      dp[k] = dp[k-2]+dp[k-1]
print(dp[N]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7  # prime number
 
def cmb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod

N,M = map(int,input().split())
ans = 1
broken = [-1]
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
for j in range(len(broken)-1):
  pattern = 0
  step = broken[j+1]-broken[j]-2
  if broken[j+1]-broken[j] == 1:
    ans = 0
    break
  step_pattern = step//2
  for k in range(step_pattern+1):
    pattern += cmb(step-k,k)
  ans = ans*pattern
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7  # prime number
 
def cmb(n, r, mod=MOD):
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod

N,M = map(int,input().split())
ans = 1
broken = [-1]
for i in range(M):
  K = int(input())
  broken.append(K)
broken.append(N+1)
for j in range(len(broken)-1):
  pattern = 0
  step = broken[j+1]-broken[j]-2
  step_pattern = step//2
  for k in range(step_pattern+1):
    pattern += cmb(step-k,k)
  ans = ans*pattern
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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
for i in range(n-1):
  if i+2 not in a:
    dp[i+2]=dp[i+1]+dp[i]
  else:
    dp[i+2]=0
print(dp[n]%(10**9+7))

Submission status: Time Limit Exceeded

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

cnt2 = 0
cnt1 = 1

for i in range(1,n):
    if i in a:
        cnt2, cnt1 = cnt1, 0
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mod = 10**9+7
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

def cnt(n):
  s = sum([comb(n-i,i,mod)%mod for i in range(n//2+1)])
  s = s%mod
  return s

A0 = 0
ans = 1
for i in range(M):
  A1 = int(input()) - 1
  ans = (ans * cnt(A1-A0))%mod
  A0 = A1+2
ans = (ans * cnt(N-A0))%mod
print(ans)

Submission status: Time Limit Exceeded

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


dp = [0] * (n+1)
mod = 10**9 + 7
# 配るdp ではなくもらうdpで書くようにしてみる

for i in range(n+1):
    if i == 0:
        dp[i] = 1

    elif i in As:
        dp[i] = 0
    elif i == 1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1] % mod + dp[i-2] % mod) % mod
    


print(dp[n])

Submission status: Time Limit Exceeded

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

dp = [0 for _ in range(N+2)]
dp[N+1] = 0
dp[N] = 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

MOD = 10**9 + 7

# dp[i]: i段目の移動方法の合計
dp = [0] * (N+1)

# 初期条件
dp[0] = 1

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

    if not (i+1) in a:
        dp[i+1] += dp[i] % MOD
    if not (i+2) in a:
        dp[i+2] += dp[i] % MOD

print(dp[-1] % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


DP=[1]*(N+1)

if 1 in a:
    DP[1]=0

for i in range(2,N+1):
    if i in a:
        DP[i]=0
        if DP[i-1]==0:
            print(0)
            exit()
    else:
        DP[i]=DP[i-1]+DP[i-2]
        DP[i]=DP[i]%mod

print(DP[N])

Submission status: Time Limit Exceeded

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

a = [int(input()) for i in range(M)]
if M == 0:  a.append(0)
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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
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) % mod
n, m = [int(i) for i in input().split()]
a = [int(input()) for _ in range(m)]
print(dp(0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
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))