Problem:


Score : 300 points

Problem Statement

There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.

However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.

How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

Sample Input 1

6 1
3

Sample Output 1

4

There are four ways to climb up the stairs, as follows:

0 \to 1 \to 2 \to 4 \to 5 \to 6

0 \to 1 \to 2 \to 4 \to 6

0 \to 2 \to 4 \to 5 \to 6

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

There may be no way to climb up the stairs without setting foot on the broken steps.

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

Be sure to print the count modulo 1\ 000\ 000\ 007.



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

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

num_goup = [1]
for s in range(1, N + 1):
    if s in A:
        num_goup.append(-1)
        continue
    
    if s == 1:
        num_goup.append(1)
        continue
    
    if num_goup[-1] == -1:
        if num_goup[-2] == -1:
            num_goup.append(-1)
        else:
            num_goup.append(num_goup[-2])
    else:
        if num_goup[-2] == -1:
            num_goup.append(num_goup[-1])
        else:
            num_goup.append(num_goup[-1] + num_goup[-2])
    
print(num_goup[-1])

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
stairs = [0] * (n + 1)
a = [int(input()) for i in range(m)]
mod = (10 ** 9 + 7)
stairs[0] = 1

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

stairs[1] = 1
for i in a:
    stairs[i] = "#"


for i in range(2, n + 1):
    if stairs[i] != "#":
        #　両方セーフ
        if stairs[i-1] != "#" and stairs[i-2] != "#":
            stairs[i] += stairs[i-1] + stairs[i-2]
        # 両方アウト
        elif stairs[i-1] == "#" and stairs[i-2] == "#":
            pass
        # 1マス前アウト
        elif stairs[i-1] == "#" and stairs[i-2] != "#":
                stairs[i] += stairs[i-2]
        # 2マス前アウト
        elif stairs[i-2] == "#" and stairs[i-1] != "#":
                stairs[i] += stairs[i-1]

        stairs[i] = stairs[i] % mod


print(stairs[n] % mod)

Submission status: Wrong Answer

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

def solve(n):
  if n == 0:
    ans = 0
  elif n == 1:
    ans = 1
  elif n == 2:
    ans = 2
  else:
    ans = solve(n-1) + solve(n-2)
  return ans

Submission status: Wrong Answer

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

mod = 10**9+7

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

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

print(max(dp[n],0))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a_list = [None] * M
for i in range(M):
    a_list[i] = int(input())
mod = 1000000007

ways = [0] * (N + 1)
ways[N] = 1
ways[N - 1] = 1
for n in reversed(range(N - 1)):
    if n in a_list:
        continue
    ways[n] = (ways[n + 1] + ways[n + 2]) % mod
print(ways[0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import stdin

MOD = 10 ** 9 + 7

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()
broken = [0] * n

for line in inp:
    a = int(line.strip())
    broken[a] = 1

dp = [0] * (n + 1)

dp[n] = dp[n - 1] = 1
for i in xrange(n - 2, -1, -1):
    if broken[i]: continue
    dp[i] = dp[i + 1] + dp[i + 2]
    if dp[i] >= MOD: dp[i] -= MOD

print dp[0] % MOD

Submission status: Wrong Answer

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

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

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


print(tmp[-1] % 1000000007)

Submission status: Wrong Answer

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

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

print( int(DP[N-1]%1000000007) )

Submission status: Wrong Answer

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

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

mod = 10**9+7

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

print(dp[0])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
dp[0] = 1
for i in range(n):
  if i+1 not in lis:dp[i+1] += dp[i]
  if i+2 not in lis:dp[i+2] += dp[i]
print(dp[n])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, m = li()
a = [ni() for _ in range(m)]
aset = set(a)

MOD = 10**9+7

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

for i in range(n):
    if i+1 in aset:
        continue

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

    dp[i+1] = dp[i] + dp[i-1]
    dp[i+1] %= MOD

print(dp[n])

Submission status: Time Limit Exceeded

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

A = [int(input()) for _ in range(M)]

lis = [0]*(N+1)
lis[0] = 1


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

print(lis[N])

Submission status: Time Limit Exceeded

Solution code:
"""
6 1
3
"""

n, m = list(map(int, input().split()))
aaa = list(int(input()) for i in range(m))

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:

n, m = list(map(int, input().split()))
aaa = list(int(input()) for i in range(m))

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

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

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 if 1 not in aaa else 0
MOD = 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
#import math
#import itertools
#import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    b_sts=[]
    for i in range(m):
        b=INT()
        b-=1
        b_sts.append(b)
    step=[0]*(n+2)
    step[1]=1
    for i in range(n):
        if i in b_sts:
            continue
        else:
            step[i+2]=(step[i+1]+step[i])%MOD
    print(step[-1]%MOD)

if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

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

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

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

print(dp[N])

Submission status: Time Limit Exceeded

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

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

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

    print(dp[N]) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

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

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

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

    print(dp[N]) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

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

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

    print(dp[N]) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

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

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

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




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

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

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

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




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    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(2,N+1):
        if (i-1 in a)&(i-2 in a):
            print(0)
            quit()

        if i-1 in a:
            dp[i] = dp[i-2]
        elif i-2 in a:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1] + dp[i-2]

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




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

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

    for i in range(2,N+1):
        if (i-1 in a)&(i-2 in a):
            print(0)
            quit()

        if i-1 in a:
            dp[i] = dp[i-2]
        elif i-2 in a:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1] + dp[i-2]

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




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

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 = [1] * (N+1)

for i in A:
    dp[i] = 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])

Submission status: Time Limit Exceeded

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

dp = [1] + [0]*n

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

def comb(n, k):
  if k > n - k:
    k = n - k
  de = 1
  nu = 1
  for i in range(k):
    de *= (n - i)
    de = de % MOD
    nu *= (i + 1)
    nu = nu % MOD
  nu = pow(nu, -1, MOD)
  return (de * nu) % MOD

ans = 1

for i in range(M):
  temp = 0
  l = int(input()) - 1
  if s > l:
    print(0)
    exit()
  step = l - s
  for j in range(1 + (step // 2)):
    temp += comb(step-j, j)
    temp = temp % MOD
  ans *= temp
  ans = ans % MOD
  s = l + 2
l = N
step = l - s
temp = 0
for i in range(1 + (step // 2)):
  temp += comb(step-i, i)
  temp = temp % MOD
ans *= temp
ans = ans % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mae = 0
sub = []
flag = False

for _ in range(M):
  broken = int(input())
  if mae == broken: # 不可能
    flag = True
  if flag:
    continue
  if mae+1 == broken:
    mae = broken + 1
    continue
  sub.append(broken-1-mae)
  mae = broken + 1
# 無理な時
if flag:
  print(0)
  exit()
# forの中で最後まで行ってない分の追加
if mae != N:
  sub.append(N-mae)

from operator import mul
from functools import reduce

# nCrの関数
def C(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
# 壊れてるやつの間の上り方の場合の数
def count(n):
  ans = 1
  for i in range(n//2):
    ans += C(n-i-1, i+1)
  return ans

ans = 1
waru = 10**9+7
for s in sub:
  ans *= count(s)%waru
print(ans%waru)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mae = 0
sub = []
flag = False

for _ in range(M):
  broken = int(input())
  if mae == broken: # 不可能
    flag = True
  if flag:
    continue
  if mae+1 == broken:
    mae = broken + 1
    continue
  sub.append(broken-1-mae)
  mae = broken + 1
# 無理な時
if flag:
  print(0)
  exit()
# forの中で最後まで行ってない分の追加
if mae != N:
  sub.append(N-mae)

from operator import mul
from functools import reduce

# nCrの関数
def C(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
# 壊れてるやつの間の上り方の場合の数
def count(n):
  ans = 1
  for i in range(n//2):
    ans += C(n-i-1, i+1)
  return ans

ans = 1
for s in sub:
  ans *= count(s)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
def nCr(n, r):
    r = min(r, n-r)
    num, den = 1, 1
    for i in range(r):
        num *= (n-i)
        den *= (i+1)
    return num // den % mod

lv = 0
a.append(n+1)
ans = 1
for v in a:
    vr = v-1 - lv
    if vr < 0:
        print(0)
        exit()
    r = 0
    for i in range(vr+(-vr//2)+1):
        r += nCr(vr-i, i)
    ans = (ans * r) % mod
    lv = v+1
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
def nCr(n, r):
    r = min(r, n-r)
    num, den = 1, 1
    for i in range(r):
        num = (num * (n-i)) % mod
        den = (den * pow(i+1, mod-2, mod)) % mod
    return num * den % mod

lv = 0
a.append(n+1)
ans = 1
for v in a:
    vr = v-1 - lv
    if vr < 0:
        print(0)
        exit()
    r = 0
    for i in range(vr+(-vr//2)+1):
        r += nCr(vr-i, i)
    ans = (ans * r) % mod
    lv = v+1
print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

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


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

print(memo[-1]%mod)

Submission status: Time Limit Exceeded

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

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


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

print(memo[-1]%mod)

Submission status: Time Limit Exceeded

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

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

mod = 1000000007

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

for i in range(1, n+1):
    if i in a:
        memo[i] = 0
    elif i <= 2:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1] + memo[i-2]
print(memo[-1]%mod)

Submission status: Time Limit Exceeded

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

p = 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])%p
    if i in a:
        dp[i] = 0
print(dp[n])

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 = 0
  for i in range(n//2+1):
    s += comb(n-i,i,mod)
    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())
a = ([int(input()) for i in range(m)])
inf = 1000000007

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

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

if __name__ == '__main__':

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

    dp = [0] * (N + 2)

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

    #print(dp)

    mod = 1000000007

    dp[N] = 1

    for i in range(N + 1):
        if (i == 0):
            continue
        i = N - i

        #print('i = ',i)

        '''
        if(i not in a):
            dp[i] += (dp[i + 1] + dp[i + 2]) % mod
            #print(dp[i])
        '''

        if (dp[i] == False):
            dp[i] += (dp[i + 1] + dp[i + 2]) % mod
            # print(dp[i])
        else:
            dp[i] = 0

    #print(a)
    print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

if __name__ == '__main__':

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

    dp = [0] * (N + 2)
    mod = 1000000007

    dp[N] = 1

    for i in range(N + 1):
        if (i == 0):
            continue
        i = N - i

        #print('i = ',i)

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

    #print(a)
    print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8

if __name__ == '__main__':

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

    dp = [0] * (N + 2)
    mod = 1000000007

    dp[N] = 1

    for i in range(N + 1):
        if (i == 0):
            continue
        i = N - i

        #print('i = ',i)

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

    #print(a)
    print(dp[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

mod=10**9+7

dp=np.zeros(N+1)
dp[0]=1
if 1 not in A:
    dp[1]=1
else:
    dp[1]=0

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

print(int(dp[N]))

Submission status: Time Limit Exceeded

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

mod=10**9+7

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

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

print(int(dp[N]))

Submission status: Time Limit Exceeded

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

mod=10**9+7

dp=np.zeros(N+1)
dp[0]=1
if 1 not in A:
    dp[1]=1
else:
    dp[1]=0

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

print(int(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

dp[0] = 1

for v in range(1,N+1):
    if v in A:
        continue
    if v == 1:
        dp[v] = (dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v-1] + dp[v-2])%(1000000007)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

dp[0] = 1

for v in range(1,N+1):
    if v in A:
        continue
    dp[v] = (dp[v] + dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v] + dp[v-2])%(1000000007)
print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

dp[0] = 1


for v in range(1,N+1):
    if v in A:
        continue
    dp[v] = (dp[v] + dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v] + dp[v-2])%(1000000007)
print(dp[N])

Submission status: Time Limit Exceeded

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

mod = 10**9+7
ans = [0]*(n+1)
ans [0] = 1
if 1 not in a: ans[1] = 1

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

Submission status: Time Limit Exceeded

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

mod=10**9+7

dp=np.zeros(N+1)
dp[0]=1
for i in range(1,N+1):
    if i in A:
        dp[i]=0
    else:
        if i==1:
            dp[i]=dp[i-1]
        else:
            dp[i]=dp[i-1]+dp[i-2]
            dp[i]=dp[i]%mod
dp[N]=dp[N]%mod
print(int(dp[N]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n, m = map(int, input().split())
l = []
a0 = 0
for i in range(m):
    a = int(input())
    if a - a0 == 0:
        print(0)
        exit()
    l.append(a - a0 - 1)
    a0 = a + 1
l.append(n - a0)
d = Counter(l)
key = list(d.keys())

def cmb(n, r):
    if r > n//2:
        r = n - r
    val = 1
    for i in range(r):
        val *= n - i
        val //= i + 1
    return val

ans = 1
for k in key:
    val = 0
    for i in range(k//2 + 1):
        val += cmb(k - i, i)
    ans *= val**d[k]
    ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n, m = map(int, input().split())
l = []
a0 = 0
for i in range(m):
    a = int(input())
    if a - a0 == 0:
        print(0)
        exit()
    l.append(a - a0 - 1)
    a0 = a + 1
l.append(n - a0)
d = Counter(l)
key = list(d.keys())

def cmb(n, r):
    if r > n//2:
        r = n - r
    val = 1
    for i in range(r):
        val *= n - i
        val //= i + 1
    return val

ans = 1
for k in key:
    val = 0
    for i in range(k//2 + 1):
        val += cmb(k - i, i)
        val %= 10**9 + 7
    ans *= val**d[k]
    ans %= 10**9 + 7
print(ans)