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
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(int(input()))
if n==1:
    if 1 in l:
        print(0)
    else:
        print(1)
    sys.exit()
ans1=0
ans2=0
if 1 in l:
    if 2 in l:
        print(0)
        sys.exit()
    else:
        ans2=1
else:
    ans1=1
    if 2 in l:
        pass
    else:
        ans2=2
ans=[0,ans1,ans2]
S=2
while S<n:
    S+=1
    if S in l:
        ans.append(0)
    else:
        ans.append((ans[-1]+ans[-2])%1000000007)
print(ans[-1])
#print(ans)

Submission status: Time Limit Exceeded

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

if n == 1:
    print(1)
elif n == 2:
    if 1 in a:
        print(1)
    else:
        print(2)
else:
    if 1 in a:
        b1 = 0
    else:
        b1 = 1
    if 2 in a:
        b2 = 0
    else:
        b2 = b1+1

    b3 = b1 + b2

    for i in range(3,n+1):
        if i in a:
            b3 = 0
        else:
            b3 = b1+b2
        if b3 > 1000000007:
            b3 = b3 % 1000000007
        b1 = b2
        b2 = b3
        if b1==b2==0:
            break

    print(b3)

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:
    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 = list(int(input()) for _ in range(m))
M = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2])%M
print(dp[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
for i in range(1, N+1):
    if i not in A:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N])

Submission status: Time Limit Exceeded

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

mod=10**9+7

dp=[0]*(N+1)

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

for i in range(0, N-1):
	if i+2 in a:
		dp[i+2]=0
	else:
		dp[i+2]+=dp[i+1]+dp[i]
	
print(dp[N]%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()))
dp = [0 for _ 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 - 2] + dp[i - 1]
print(dp[n] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

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

MOD = 1000000007

dict = defaultdict(int)

for i in range(M):
    if i >= 1 and a[i] - a[i - 1] == 1:
        print("0")
        exit()

dict[0] = 1
for i in range(N):
    if not i in a:
        dict[i + 1] += dict[i]
        dict[i + 2] += dict[i]
    else:
        a.pop(0)


print(dict[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

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

MOD = 1000000007

dict = defaultdict(int)

for i in range(M):
    if i >= 1 and a[i] - a[i - 1] == 1:
        print("0")
        exit()

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


print(dict[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

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

MOD = 1000000007

dict = defaultdict(int)
ans = 1
for i in range(M):
    dict[a[i]] = -10 ** 1000000000
    if i >= 1 and a[i] - a[i - 1] == 1:
        print("0")
        exit()

dict[0] = 1
for i in range(N):
    if dict[i] > 0:
        dict[i + 1] += dict[i]
        dict[i + 2] += dict[i]


print(dict[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, M = [int(x) for x in input().split()]
a = []

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

MOD = 1000000007

dict = defaultdict(int)
ans = 1
dict[0] = 1
for i in range(N):
    if not a.count(i + 1):
        dict[i + 1] += dict[i]
    if not a.count(i + 2):
        dict[i + 2] += dict[i]
    if a.count(i + 1) and a.count(i + 2):
        print("0")
        exit()


print(dict[N] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,m = MAP()
a = [INT() for _ in range(m)]

def fib(n):
    if (n==1) or (n==2):
        return 1
    else:
        return fib(n-1)+fib(n-2)

start = 0
ans = 1

for k in a:
    tmp = k-start
    if tmp==0:
        print(0)
        exit(0)
    ans *= fib(tmp)
    ans%=MOD
    start = k+1

ans*=fib(n-start+1)
ans%=MOD

print(ans)

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

Submission status: Time Limit Exceeded

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

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if n not in A:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # n in A:
    C[n+2] = 0

ans = C[N+2]  % 1000000007
print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    sys.exit()
if 1 in a:
  nlist.append(0)
  nlist.append(1)
elif 2 in a:
  nlist.append(1)
  nlist.append(0)
else:
  nlist.append(1)
  nlist.append(2)

for i in range(2,n):
  if i+1 in a:
    nlist.append(0)
  else:
    nlist.append((nlist[i-1]+nlist[i-2])%1000000007)
print(nlist[n-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

for i in range(1,m):
  if a[i]-a[i-1]==1:
    print(0)
    sys.exit()
if 1 in a:
  nlist.append(0)
  nlist.append(1)
elif 2 in a:
  nlist.append(1)
  nlist.append(0)
else:
  nlist.append(1)
  nlist.append(2)

for i in range(2,n):
  if i+1 in a:
    nlist.append(0)
  else:
    nlist.append(nlist[i-1]+nlist[i-2])
print(nlist[n-1]%1000000007)

Submission status: Time Limit Exceeded

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

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


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

for i in range(0, N, 1):

    if i+1 == 1 and not (i+1) in A:
        dp[i+1] = dp[i]
    elif not (i+1 in A) and not(i in A) and not(i-1 in A):
        dp[i+1] = dp[i] + dp[i-1] 
    elif not(i+1 in A) and not (i in A) and (i-1 in A):
        dp[i+1] = dp[i]
    elif not(i+1 in A) and (i in A) and not(i-1 in A):
        dp[i+1] = dp[i-1] 

print(dp[N]%1000000007)

Submission status: Time Limit Exceeded

Solution code:

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

dp = [1] * (N + 1)

flag = 0
for i in range(N-1):
    if i+1 in a and i in a:
        flag = 1
        break
    elif i+1 in a:
        dp[i+2] = dp[i]
    elif i in a:
        dp[i+2] = dp[i+1]
    else:
        dp[i+2] = (dp[i+1] + dp[i]) % mod

if flag == 1:
    print(0)
else:
    print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
import math

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

dp = [1] * (N + 1)

flag = 0
for i in range(N-1):
    if i+1 in a and i in a:
        flag = 1
        break
    elif i+1 in a:
        dp[i+2] = dp[i]
    elif i in a:
        dp[i+2] = dp[i+1]
    else:
        dp[i+2] = dp[i+1] + dp[i]

if flag == 1:
    print(0)
else:
    print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1 or tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

if M == 0:
    print(calc(0,N))
else:
    flag = 0

    A = calc(0,a[0]-1)

    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            flag = 1
            break
        A *= calc(a[i]+1,a[i+1]-1)
        A %= mod

    A *= calc(a[M-1]+1,N)
    A %= mod

    if flag == 1:
        print(0)
    else:
        print(A)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1:
        return 1
    if tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

if M == 0:
    print(calc(0,N))
else:
    flag = 0
    A = 1
    A *= calc(0,a[0]-1)

    for i in range(M-1):
        if a[i] + 1 == a[i+1]:
            flag = 1
            break
        A *= calc(a[i]+1,a[i+1]-1)
        A %= mod

    A *= calc(a[M-1]+1,N)
    A %= mod

    if flag == 1:
        print(0)
    else:
        print(A)

Submission status: Time Limit Exceeded

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

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

dp = [0]*(N+3)



for i in range(N+1):

    if i==0:
        if not (i+1) in A:
            dp[i+1] = 1 + dp[i]
        if not (i+2) in A:
            dp[i+2] = 1 + dp[i]
        continue 
    if not i+1 in A:
        dp[i+1] = dp[i] + dp[i+1]
    if not i+2 in A:
        dp[i+2] = dp[i] + dp[i+2]

print(dp[N]%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def calc(f,t):
    tmp = t - f
    i = 1
    ans = 1
    if tmp == 1:
        return 1
    if tmp == 0:
        return 1
    while(tmp >= 2*i):
        ans += math.factorial(tmp - i) // math.factorial(i) // math.factorial(tmp - 2*i)
        i += 1
    return ans

flag = 0
A = 1
if M > 0:
    A *= calc(0,a[0]-1)

for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        flag = 1
        break
    A *= calc(a[i]+1,a[i+1]-1)
    A %= mod

if M > 0:
    A *= calc(a[M-1]+1,N)
    A %= mod

if flag == 1:
    print(0)
elif M == 0:
    print(calc(0,N))
else:
    print(A)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def main():
    N,M = map(int,input().split())
    A = [int(input()) for _ in range(M)]
    MOD = 1000000007
    ans = [1]
    ans.append(0) if 1 in A else ans.append(1)
    for i in range(2,N+1):
        ans.append(0)
        if i in A:
            continue
        ans[i] += (ans[i-1] + ans[i-2])
    print(ans[N] % MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    a = [int(input().rstrip('\n')) for _ in range(m)]
    x = [0] * (n + 1)
    x[0] = 1 if 0 not in a else 0
    x[1] = 1 if 1 not in a else 0
    for i in range(2, n+1):
        if i not in a:
            x[i] = (x[i-1] + x[i-2]) % 1000000007
        else:
            x[i] = 0
    print(x[-1])


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
for i in range(0,M-1):
    if A[i+1] - A[i] == 1:
        print(0)
        sys.exit()
if not 1 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        memo[i] = (memo[i - 1] + memo[i - 2]) % lim
print(memo[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
for i in range(0,M-1):
    if A[i+1] - A[i] == 1:
        print(0)
        sys.exit()
if not 2 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        if not ((i-1 in A) or (i-2 in A)):
            memo[i] = (memo[i - 1] + memo[i - 2]) % lim
        elif i-1 in A:
            memo[i] = memo[i - 2]
        elif i-2 in A:
            memo[i] = memo[i - 1]
        elif (i-1 in A) and (i-2 in A):
            print(0)
            sys.exit()
print(memo[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
if not 2 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        if not ((i-1 in A) or (i-2 in A)):
            memo[i] = (memo[i - 1] + memo[i - 2])
        elif i-1 in A:
            memo[i] = memo[i - 2]
        elif i-2 in A:
            memo[i] = memo[i - 1]
        elif (i-1 in A) and (i-2 in A):
            print(0)
            sys.exit()
print(memo[-1] % lim)

Submission status: Time Limit Exceeded

Solution code:
#!/home/ryo/.pyenv/versions/anaconda3-2019.03/envs/hoge/bin/python
import sys

lim=10**9+7
N,M = map(int,input().split())
A=[]
for i in range(0,M):
    A.append(int(input()))

memo = [0] * (N+1)
memo[0]=1
if not 2 in A:
    memo[1]=1
for i in range(2, N+1):
    if not i in A:
        if not ((i-1 in A) or (i-2 in A)):
            memo[i] = (memo[i - 1] + memo[i - 2]) % lim
        elif i-1 in A:
            memo[i] = memo[i - 2]
        elif i-2 in A:
            memo[i] = memo[i - 1]
        elif (i-1 in A) and (i-2 in A):
            print(0)
            sys.exit()
print(memo[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if i in a:
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = fibs[1] + fibs[0]
    if next > 1000000007:
      next -= 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if i in a:
    fibs[0] = fibs[1]
    fibs[1] = 0
  else:
    next = (fibs[1] + fibs[0]) % 1000000007
    fibs[0] = fibs[1]
    fibs[1] = next

print(fibs[-1])

Submission status: Time Limit Exceeded

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

if 1 in a:
  fibs = [1,0]
else:
  fibs = [1,1]

for i in range(2,N+1):
  if i in a:
    fibs.append(0)
  else:
    fibs.append((fibs[i-1] + fibs[i-2]) % 1000000007)

print(fibs[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

dp[0]=1

for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % big_prime #dp[-1]=0
    if i in list_a:
        dp[i]=0
ans = dp[n]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

dp[0]=1

for i in range(1,n+1):
    dp[i] = dp[i-1] + dp[i-2] #dp[-1]=0
    if i in list_a:
        dp[i]=0
ans = dp[n] % big_prime
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

dp[0]=1

for i in range(1,n+1):
    if i in list_a:
        dp[i]=0
    else:
        dp[i] = dp[i-1] + dp[i-2] #dp[-1]=0
ans = dp[n] % big_prime
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

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


for i in range(2,n+1):
    if i in list_a:
        dp[i]=0
    else:
        dp[i] = dp[i-1] + dp[i-2]
ans = dp[n] % big_prime
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        a = [int(input()) for _ in range(M)]
        
        if (1 in a):
            f = [1, 0]
        else:
            f = [1, 1]
            
        for i in range(2, N+1):
            if i in a:
                f.append(0)
            else:
                f.append((f[i-1] + f[i-2])%1000000007)
        
        print(f[N])
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        a = [int(input()) for _ in range(M)]
        
        if (1 in a):
            f = [1, 0]
        else:
            f = [1, 1]
            
        for i in range(2, N+1):
            if i in a:
                f.append(0)
            else:
                f.append(f[i-1] + f[i-2])
        
        print(f[N]%1000000007)
    except:
        break

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(1, N+1):
    if i == 1:
        if 1 not in a_list:
            ans_list[1] += ans_list[i-1]
    else:
        if i not in a_list:
            ans_list[i] += ans_list[i-2]
            ans_list[i] += ans_list[i-1]

print(int(ans_list[-1]%1000000007))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if i in a:
        continue
    else:
        if i+1 not in a and i+1 <= N:
            dp[i+1] += dp[i]
        if i+2 not in a and i+2 <= N:
            dp[i+2] += dp[i]
print(dp[-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n+1)
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:dp[i]=0
print(dp[n])

Submission status: Time Limit Exceeded

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

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

print(arr[-1])

Submission status: Time Limit Exceeded

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


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

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

print(dp[-1])

Submission status: Time Limit Exceeded

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

print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
ans=1
mod =10**9+7
dp = [1]
for i in range(1,N+1):
  if i in a:
    dp.append(0)
  else:
    if i ==1:
      dp.append(dp[i-1])
    else:
      dp.append((dp[i-1]+dp[i-2])%mod)

print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
ans=1
mod =10**9+7
dp = [0 for i in range(N+1)]
dp[0]=1
for i in range(1,N+1):
  if i not in a:
    if i==1:
      dp[i] = dp[i-1]
    else:
      dp[i] = dp[i-1]+dp[i-2]
  
print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
ans=1
mod =10**9+7
dp = [0 for i in range(N+1)]
dp[0]=1
for i in range(1,N+1):
  if i not in a:
    if i==1:
      dp[i] = dp[i-1]%mod
    else:
      dp[i] = (dp[i-1]%mod+dp[i-2]%mod)%mod
  
print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
ans=1
mod =10**9+7
dp = [0 for i in range(N+1)]
dp[0]=1
for i in range(1,N+1):
  if i not in a:
    if i==1:
      dp[i] = dp[i-1]%mod
    else:
      dp[i] = dp[i-1]%mod+dp[i-2]%mod
  
print(dp[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

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

dp = []
for i in range(N + 1):
    dp.append(None)
dp.append(0)

dp[N] = 1

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

# print('dp', dp)
print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

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

dp = []
for i in range(N + 1):
    dp.append(None)
dp.append(0)

dp[N] = 1

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

# print('dp', dp)
print(dp[0] % 1000000007)

Submission status: Time Limit Exceeded

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

ans = [0,1]

for n in range(1,N+1):
  if n in broken_list:
    ans.append(0)
  else:
    ans.append((ans[-2]+ans[-1]) % MOD)

print(ans[-1] % MOD)

Submission status: Time Limit Exceeded

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

ans = [0,1]

for n in range(1,N+1):
  if n in broken_list:
    ans.append(0)
  else:
    ans.append(ans[-2]+ans[-1])

print(ans[-1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
# ここから
import sys
input = sys.stdin.readline

def resolve():
    n, m = map(int, input().split())
    aa = [int(input()) for _ in range(m)]
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 0 if 1 in aa else 1

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

    print(dp[n])



resolve()

Submission status: Time Limit Exceeded

Solution code:
nm=list(map(int,input().split()))
lista=[]#壊れている階段の座標
for i in range(nm[1]):
    lista=lista+[int(input())]
i=0#現在地
b1=1#現在地までの行き方
b2=0#現在地のひとつ前までの行き方
while i <nm[0]:
    if i+1 not in lista:
        i+=1
        b1+=b2
        b2=b1-b2
    elif i+1 in lista and i+2 not in lista:
        i+=2
        b2=0
    else:
        i=nm[0]
        b1=0
print(b1%1000000007)

Submission status: Time Limit Exceeded

Solution code:
Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]
b_append = b.append
for i in range(1,N+1):
    if i in a:
        b.append(0)
        continue
    if i == 1:
        b.append(1)
        continue
    b.append(b[i-1]+b[i-2])
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])

Submission status: Time Limit Exceeded

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