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:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

MOD = 10**9+7

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

for i in range(n+1):
    if i == 0 or i == 1:
        if i in a:
            step[i] = 0
    else:
        step[i] = step[i-1] + step[i-2]
        if i in a:
            step[i] = 0
        step[i] %= MOD

print(step[-1])

Submission status: Time Limit Exceeded

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

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

print(l[N])

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
ls = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    if i not in ls:
        dp[i] = (dp[i-1]+dp[i-2])
        if dp[i] >= 10**9+7:
            dp[i] %= 10**9+7 
    else:
        if i-1 in ls:
            print(0)
            sys.exit()
print(dp[-1])

Submission status: Time Limit Exceeded

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

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 == 1:
        if not i - 1 in a:
            dp[i] = 1
    else:    
        if not i - 1 in a:
            dp[i] += dp[i - 1] % MOD
        if not i - 2 in a:
            dp[i] += dp[i - 2] % MOD
print(dp[-1] % MOD)

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_)
  
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
    continue
  dp[i]=dp[i-1]+dp[i-2]
#print(dp)
print(dp[n]%(1000000007))

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_)
  
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
    continue
  dp[i]=dp[i-1]+dp[i-2]
#print(dp)
print(dp[n]%(1000000007))

Submission status: Time Limit Exceeded

Solution code:

n,m  = map(int,input().split())
ln = []
mod_1 = 10**9 + 7
for i in range(m):
    ln.append(int(input()))
line = []
for i in range(n+1):
    if  i in ln:
        line.append(0)
    elif i == 0:
        line.append(1)
    elif i == 1:
        line.append(1)
    else:
        line.append((line[-1] + line[-2]) % mod_1)
print(line[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n, m =map(int,input().split())
a=[int(input()) for _ in range(m)]
lis={0:1}
def saiki(x):
  if x not in lis:
      if x in a:
        lis[x]=0
        return 0
      elif x==1:
        lis[1]=1
        return 1
      else:
        d=saiki(x-1)+saiki(x-2)
        if d >10**9+7:
          lis[x]= d % (10**9+7)
          return lis[x]
        else:
          lis[x]=d
          return d
  else:
    return lis[x]
      
print(saiki(n))

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
mod = 1000000007
a = list(int(input()) for _ 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 not in a: dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
mod = 1000000007
a = tuple(int(input()) for _ 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 in a: continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
mod = 1000000007
a = tuple(int(input()) for _ 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 in a: continue
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]
    mod = 1000000007

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

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

    ans = dp[n] % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]
    mod = 1000000007

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

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

    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]
    mod = 1000000007

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

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

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

    ans = dp[-1] % 1000000007
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
li = [int(input()) for i in range(m)] #壊れている段
ans = [1] #0段目にいる通り

for i in range(1,n+1): 
    if i in li:
        ans.append(0)
        li.remove(i)
    else:
        if i == 1:
            ans.append(1)
        else:
            ans.append(ans[i-2]+ans[i-1])

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
li = [int(input()) for i in range(m)] #壊れている段
ans = [1] #0段目にいる通り

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

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

Submission status: Time Limit Exceeded

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

nums = [0]*(N+1)
nums[0] = 1
if 1 not in a:
    nums[1] = 1
for i in range(2, N+1):
    if not i in a:
      nums[i] = nums[i-1] + nums[i-2]

print(nums[N]%(1000000007))

Submission status: Time Limit Exceeded

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

mod = 1000000007
nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1
for i in range(2,n+1):
  if i in a: continue
  nums[i] = nums[i-1] + nums[i-2]

print(nums[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
# f(x) = f(x - 1) + f(x - 2)の場合のdp
def f_dp(x, a):
    dp = [0 for i in range(x + 1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, x + 1):
        if i not in a:
            dp[i] = dp[i - 1] + dp[i -2]
    return dp[n] % MOD

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [int(input()) for i in range(m)]

    dp = f_dp(n, a)
    print(dp)

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
broken_steps = [int(input()) for _ in range(m)]
#print(broken_steps)

def ptn_num(x): # 'x'stepまでのパターン数
    if x == 1:
        print(1)
    else:
        dp = [0] * (x+1) # DP枠_including step'0'
        cnt = 0
        if 1 in broken_steps: # in case, step'1' broken 
            dp[:2] = 1, 0
        else:
            dp[:2] = 1, 1 # Usually

        for i in range(2, x+1):
            if i in broken_steps: # 階段が壊れている場合...
                cnt += 1
                if cnt == 2:
                    print(0)
                    exit()
            else: # 階段が壊れてない場合...
                dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
                cnt = 0
        
        print(dp[-1])

ptn_num(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())
A = []
MOD = 10**9+7
memo = {}
for _ in range(M):
  A.append(int(input()))
def step(cur):
  if cur in memo:
    return memo[cur]
  if cur == N:
    memo[cur] = 1
    return memo[cur]
  if cur > N or cur in A:
    memo[cur] = 0
    return memo[cur]

  memo[cur] = (step(cur+1) + step(cur+2))%MOD
  return memo[cur]

print(step(0)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

def main():
    # n, m = map(int, input().split())
    # a = [int(input()) for i in range(m)]
    n, m = map(int, readline().split())
    a = list(map(int, read().split()))
    mod = 1000000007

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = (d[i-1] + d[i-2]) % mod
            cnt = 0
    # print(d)  
    ans = d[n]        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # 2回0が続く状況aに連番があったら即座に終了する
    cnt = 0 
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 not in a:
        d[1] = 1
    # else:
    #     d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    for i in range(2, n+1):
        if i in a:
            d[i] = 0
            cnt += 1
            if cnt == 2:
                print('0')
                exit()
        else:
            d[i] = d[i-1] + d[i-2]
            cnt = 0
    # print(d)  
    ans = d[n] % mod        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

n, m = map(int, readline().split())
a = list(map(int, read().split()))

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
cnt = 0
for i in range(2, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
        cnt = 0
    else:
        cnt += 1
        if cnt == 2:
            print('0')
            exit()
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m = map(int, readline().split())
a = list(map(int, read().split()))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n, m = map(int, readline().split())
a = list(map(int, read().split()))

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

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

Submission status: Time Limit Exceeded

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

    mod = 1000000007
    # フィボナッチ数列を作る要領で行う
    d = [0] * (n+1)
    # d[0]とd[1]を規定。aに1が含まれていることを考慮して場合分けしておく
    d[0] = 1
    if 1 in a:
        d[1] = 0
    else:
        d[1] = 1
    # 階段番号は2~nまでを見る必要がある
    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)  
    ans = d[n] % mod        
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
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]%1000000007)

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]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
    if i-1 not in a and i-2 not in a:
        dp[i]=dp[i-1]+dp[i-2]
    elif i-1 in a and i-2 not in a:
        dp[i]=dp[i-2]
    elif i-1 not in a and i-2 in a:
        dp[i]=dp[i-1]
    elif i-1 in a and i-2 in a:
        dp[i]=0
print(dp[n]%1000000007)

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

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 + 2)
DP[0] = 1
for i in range(0, N):
  if i in A:
    continue
  if not i + 1 in A:
    DP[i + 1] += DP[i]
  if not i + 2 in A:
    DP[i + 2] += DP[i]

print(DP[N]%mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = []
for m in range(M):
    A.append(int(input()))
    
dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

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

Submission status: Time Limit Exceeded

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

dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

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

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
memo = deque([1])
mcnt = 1
def fact(x):
    global memo,mcnt
    if x == 0: return 1
    while x > mcnt:
        memo.append(memo[-1] * (mcnt + 1))
        mcnt += 1
    return memo[x-1]

CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    way = 0
    for two in range(v//2+1):
        one = v - two * 2
        comb = (fact(one+two) // (fact(one) * fact(two))) % CONST
        way = (way + comb) % CONST
    ans = (ans * way) % CONST
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    way = 0
    for two in range(v//2+1):
        one = v - two * 2
        comb = (math.factorial(one+two) // (math.factorial(one) * math.factorial(two))) % CONST
        way = (way + comb) % CONST
    ans = (ans * way) % CONST
print(ans)

Submission status: Time Limit Exceeded

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

if n ==  1 and m == 0:
  print(1)
  exit()
  
if 1 not in a:
  lis.append(1)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(2)
    
elif 1 in a:
  lis.append(0)
  if 2 in a:
    lis.append(0)
  else:
    lis.append(1)


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m = map(int, input().split())
A = []
for i in range(m):
    A.append(int(input()))
dp = [0] * (n+1)
mod = 1000000007
dp[0] = 1
if 1 in A:
    if 2 in A:
        print(0)
        sys.exit()
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:
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(N+10)
B[0]=1
for i in range(N+4):
    if i==1:
        if 1 in A:
            B[1]=0
        else:
            B[i]=1
    else:
        if i in A:
            B[i] = 0
        else:
            B[i] += B[i-1]+B[i-2]
            B[i] %= (10**9+7)
print(B[N]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
# input
stairs, broken = map(int, input().split())
broken_list = []
for i in range(broken):
  broken_list.append(int(input()))
  
# main
goalable = True
for i in range(1, broken):
  if broken_list[i-1] == broken_list[i]-1:
    goalable = False
    break

if goalable:
  broken_list.append(stairs+1)
  now = 0
  ans_list = []
  for b in broken_list:
    cp = b - 1
    stg = cp - now
    tmp = 0
    
    if stg != 0:
      for x in range(stg+1):
        if (stg - x) % 2 == 0:
          y = (stg - x) // 2
          tmp += math.factorial(x+y) // (math.factorial(x) * math.factorial(y))
      ans_list.append(tmp)
    else:
      ans_list.append(1)
    now = b + 1
  
  ans = 1
  for i in ans_list:
    ans = (i * ans) % 1000000007
  print(ans)
else:
  print(0)

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

for i in range(2, n + 1):
    if (i in a):
        #dp[i] = 0
        continue
    elif (dp[i - 1] == 0 and dp[i - 2] == 0):
        print(0)
        exit()
    else:
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD


#print(dp[n] % MOD)
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
if (1 in a):
    dp[1] = 0
else:
    dp[1] = 1
# dp approach

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


print(dp[n] % MOD)

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

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] % MOD)

Submission status: Time Limit Exceeded

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

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

for i in range(2, n+1):
    if i in a:
        continue

    # 到達不可能
    if res[i-1] == 0 and res[i-2] == 0:
        break

    res[i] = (res[i-1] % MOD + res[i-2] % MOD) % MOD

print(res[-1])

Submission status: Time Limit Exceeded

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

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

for i in range(2, n+1):
    if i in a:
        continue

    # 到達不可能
    if res[i-1] == 0 and res[i-2] == 0:
        break

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

print(res[-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 13:40:00 2020

@author: NEC-PCuser
"""
def fibonatch(a, N):
    #d[i][j]: iからjへの最短距離
    n1, n2 = 1, 1
    if N == 0:
        return 1
    elif N == 1:
        return 1
    else:
        for i in range(N - 1):
            if str(i) in a:
                n2 = 0
            if str(i + 1) in a:
                n1 = 0
            n1, n2 = n1 + n2, n1
        return (n1) % 1000000007



if __name__ == "__main__":
    N, M = map(int, input().split())
    a = []
    for i in range(M):
        a.append(input())
    
    print(fibonatch(a, N))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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
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(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import sys
 
N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(1 , M+1) :
    a = int(input())
    brake.append(a)
 
for i in range(1, N+1) :
    if i in brake :
        brake.pop(0)
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
    
print(stair[N])

Submission status: Time Limit Exceeded

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

for i in range(1, N+1) :
    if i in brake :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

N , M = (int(a) for a in input().split())
stair = [1]
brake = []
for i in range(1 , M+1) :
    a = int(input())
    brake.append(a)

for i in range(1, N+1) :
    if i in brake :
        stair.append(0)
    elif i == 1 : 
        stair.append(1) 
    else : stair.append((stair[i-1] + stair[i-2]) % (10**9+7))
         
print(stair[N])

Submission status: Time Limit Exceeded

Solution code:
import sys

N , M = (int(a) for a in input().split())
stair = [0]*(N+1)
stair[0] = 1
brake = []
for i in range(1 , M+1) :
    a = int(input())
    brake.append(a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
MOD = 10**9 + 7
n, m = map(int, input().split())
a = [int(x) for x in sys.stdin.readlines()]
ans = [0 for i in range(n)]
if 1 not in a:
    ans[0] = 1
if 2 not in a and n >=2:
    ans[1] = ans[0] + 1

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

print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
# ABC_129 C

def stairs(n, a):
    num_list = [i for i in range(n+1) if i not in a]
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in num_list:
        if i > 1:
            dp[i] = dp[i-1] + dp[i-2]

    result = dp[n] % 1000000007

    print(result)


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

if __name__ == '__main__':
    stairs(n, a)

Submission status: Time Limit Exceeded

Solution code:
# ABC_129 C

def stairs(n, a):
    dp = [0 for _ in range(n+1)]
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    for i in range(2, n+1):
        if i in a:
            continue
        dp[i] = dp[i-1]
        dp[i] += dp[i-2]

    result = dp[n] % 1000000007

    print(result)


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

if __name__ == '__main__':
    stairs(n, a)

Submission status: Time Limit Exceeded

Solution code:
# ABC_129 C

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

    result = dp[n] % 1000000007

    print(result)


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

if __name__ == '__main__':
    stairs(n, a)

Submission status: Time Limit Exceeded

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

"""
DPを考える
"""

result = [0] * (N+1)
result[0] = 1
mod = 10**9 + 7
for i in range(N+1):
    if i not in A:
        if i >= 2:
            result[i] = (result[i-1] + result[i-2])%mod
        if i == 1:
            result[i] = 1

print(result[N])

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(a, b):
    return math.factorial(a) // (math.factorial(b) * math.factorial(a - b))

n, m = map(int, input().split())
ans = 1
p = 0
for _ in range(m):
    a = int(input())
    cnt = 0
    if a == p:
        print(0)
        exit()
    s = a - 1 - p
    for i in range(s // 2 + 1):
        cnt += comb(s - i, i)
    p = a + 1
    ans = (ans * cnt) % (10 ** 9 + 7)
s = n - p
cnt = 0
for i in range(s // 2 + 1):
    cnt += comb(s - i, i)
ans = (ans * cnt) % (10 ** 9 + 7)
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)
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)]
mod=10**9+7
#Dynamic Programming
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])%mod
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
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]
ans=dp[N]%mod
print(ans)