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_list = []
for i in range(m):
    a_list.append(int(input()))

# memo = [-1 for _ in range(n)]
step_now = 0
step_1   = 0
step_2   = 0
DIV_NUM = 1000000007
if 1 in a_list:
    step_now = 0
else:
    step_now = 1
for i in range(1, n):
    if i == 1:
        step_1 = step_now
        if i+1 in a_list:
            step_now = 0
        else:
#             memo[i] = (memo[0] + 1) % DIV_NUM
            step_now = step_1 + 1
    else:
        step_2 = step_1
        step_1 = step_now % DIV_NUM
        if i+1 in a_list:
            step_now = 0
        else:
#             memo[i] = (memo[i-1] + memo[i-2]) % DIV_NUM
            step_now = (step_1 + step_2) % DIV_NUM

print(step_now)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))
s =[]
if 1 in a:
    s.append(0)
else:
    s.append(1)
if 2 in a:
    s.append(0)
else:
    s.append(1+s[0])
for i in range(2,n):
    if i+1 in a:
        s.append(0)
    elif i in a:
        s.append(s[i-2])
    elif i-1 in a:
        s.append(s[i-1])
    else:
        s.append(s[i-1] + s[i-2])
print(s[n-1] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

n, m = [int(i) for i in input().split()]


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


a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += combi(k - i, i) % 1000000007
    ans = ans * cnt % 1000000007
    if ans == 0:
        break
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#N = int(input())
INF = 1000000007
N,M = map(int,input().split())
a_list = [-1]
for i in range(M):
    a_list.append(int(input()))
a_list.append(N+1)
a_list.sort()
sa_list = []
for i in range(1,M+2):
    sa_list.append(a_list[i]-a_list[i-1])

def fibonacci(n):
    if (n<=1):
        return (n)
    else:
        return(fibonacci(n-1) + fibonacci(n-2))
n=max(sa_list)+2
fib_list=[]
for i in range(n-1):
    fib_list.append(fibonacci(i))
ans = 1
for sa_i in range(len(sa_list)):
    sa = sa_list[sa_i]
#    print(sa)
    ans = ans*fib_list[sa-1]
    ans = ans % INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(100000000)

def dfs(x):
  if x == N:
    return 1
  if x > N or x in a:
    return 0
  if memo.get(x):
    return memo[x]
  memo[x] = dfs(x+1) + dfs(x+2)
  return memo[x]

N, M = map(lambda x: int(x), input().split())
a = [int(input()) for i in range(M)]
#print(N)
#print(M)
#print(a)
memo = {}
count = dfs(0)
print(count%1000000007)

Submission status: Time Limit Exceeded

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

n, m = list(map(int, input().rstrip().split()))
lst = list(map(int, [input().rstrip() for _ in range(m)]))
MOD = 10 ** 9 + 7

if 0 in lst:
    ans = [0, 1] + [0] * (n - 1)
if 1 in lst:
    ans = [1, 0] + [0] * (n - 1)
else:
    ans = [1, 1] + [0] * (n - 1)

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

Submission status: Time Limit Exceeded

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

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

memo = {}


def step(now):
    if memo.get(now) != None:
        return memo[now]
    if now in a:
        return 0
    # print(now)
    if now == n:
        return 1
    if now > n:
        return 0
    # print(now)
    memo[now] = step(now+1)+step(now+2)
    return memo[now]


print(step(0) % 1000000007)

Submission status: Time Limit Exceeded

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

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


f=0
for i in a:
    if i+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

ways = [0] * (n+1)
ways[0] = 1
keep = 1
noway = False
for i in range(1, n+1):
  if i in broken:
    if i-1 in broken:
      noway = True
      break
    ways[i] = ways[i-1]
    keep = 0
  else:
    if keep == 2:
      ways[i] = ways[i-1] + ways[i-2]
    else:
      ways[i] = ways[i-1]
      keep += 1
      
print(ways[-1] % 1000000007 if not noway else 0)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=list(int(input()) for _ in range(M) )
ans=0
ansn1=0
ansn2=0
mod=1000000007
for i in range(N):

    if i>=2 and  i+1 not in a:
        ans=(ansn1+ansn2)%mod
        ansn2 = ansn1
        ansn1=ans
        continue

    elif i+1 in a:
        ans = 0
        ansn2 = ansn1
        ansn1 = ans
        continue


    if i==0:
        if i+1 not in a:
            ans=1
            ansn2 = 0
            ansn1=ans

    elif i==1:
        if i+1 not in a:
            ans=1+ansn1
            ansn2 = ansn1
            ansn1=ans
        else:
            ans=0
            ansn2=ansn1
            ansn1=ans


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
if m >(n//2+1):
    print(0)
    exit()
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
for num in bl:
    l.remove(num)
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

ans = 1
for i in range(1, len(a_list)):
    sub = a_list[i] - a_list[i-1] - 1
    if i > 1 and sub == 0:
        print(0)
        sys.exit()
    if sub <= 2:
        continue
    sub -= 1
    count = 0
    for j in range(sub // 2 + 1):
        count += math.factorial(sub - j) // math.factorial(j) // math.factorial(sub - j * 2)
    ans *= count
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

n, m = [int(i) for i in input().split()]


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


a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += combi(k - i, i) % 1000000007
    ans = ans * cnt % 1000000007

print(ans)

Submission status: Time Limit Exceeded

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

a = 1
b = 0 if 1 in broken_list else 1

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in range(2, n+1):
  if i in broken_list:
    a, b = b, 0
  else:
    a, b = b, a + b

print(b%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

patterns = []
for i in range(1, len(a_list)):
    sub = a_list[i] - a_list[i-1] - 1
    if i > 1 and sub == 0:
        print(0)
        sys.exit()
    if sub <= 2:
        continue
    sub -= 1
    count = 0
    for j in range(sub // 2 + 1):
        count += math.factorial(sub - j) // math.factorial(j) // math.factorial(sub - j * 2)
    patterns.append(count)
count = 1
for p in patterns:
    count *= p
print(count % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#入力取得
from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
  if (n == 0):
    return (Fraction(1), Fraction(1));
  if (n % 2 == 0):
    return fibExp(fibMul(fn, fn), n / 2);
  return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a - c, b - d)

def fibMain(n):
  fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
  fibNum2 = (Fraction(1, 2), Fraction(-1, 2))

  fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n))
  fibNum4 = (Fraction(0, 1), Fraction(1, 5))
  return fibMul(fibNum3, fibNum4)

def fib(n):
  return fibMain(n)[0].numerator





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

a= []

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

l = ["1"] * (N + 1)

for a_ele in a:
    l[a_ele] = "0"

l = ''.join(l)

# print(l)

if '00' in l:
    print(0)

else:
    l_arr = l.split('0')
    result = 1
    for l_ele in l_arr:
        result *= fib(len(l_ele))
        result = result % 1000000007

    print(result)

Submission status: Time Limit Exceeded

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

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

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

print(A[N])

Submission status: Time Limit Exceeded

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

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)
if al>0:
    a.sort()

f=0
for i in a:
    if i+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=dp[i-1]%mod+dp[i-2]%mod
    print(dp[n]%mod)

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())
    



def fib(n):
    memo = [0] * (int(n)+1)
    memo[0] = 1
    for i in range(1,n+1):
        if i in a:
          memo[i] = 0
        ## memo[i] i 番目の階段にいくまでのルート数
        else:
          memo[i] = memo[i-1] +memo[i-2]
    return memo[n]

print(fib(N) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math

n, m = [int(i) for i in input().split()]


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


a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += combi(k - i, i)
    ans = ans * cnt % 1000000007

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=list(int(input()) for _ in range(M) )
ans=0
ansn1=0
ansn2=0
mod=1000000007
for i in range(N):
    if i==0:
        if i+1 not in a:
            ans=1
            ansn2 = 0
            ansn1=ans

    elif i==1:
        if i+1 not in a:
            ans=1+ansn1
            ansn2 = ansn1
            ansn1=ans
        else:
            ans=0
            ansn2=ansn1
            ansn1=ans

    elif i+1 not in a:
        ans=(ansn1+ansn2)%mod
        ansn2 = ansn1
        ansn1=ans

    else:
        ans=0
        ansn2 = ansn1
        ansn1=ans

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,m = map(int,input().split())
# 差が0だと通れない
tmp=10000000
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
    if abs(tmp-a)==1:
        print(0)
        exit()
    tmp=a

cntmap={0:1}

def count(now,s,e):
    if now > e:
        return 0
    if now == e:
        return 1
    cnt=0
    cnt+=count(now+1,s,e)
    cnt+=count(now+2,s,e)
    return cnt


c_mod=1000000007
start=0
end=0
ans=1
for a in a_list:
    # 各部分の移動方法
    end=a-1
    if (end-start) in cntmap:
        ans=ans*cntmap[end-start]%c_mod
    else:
        res=count(start,start,end)
        cntmap[end-start]=res
        ans=ans*res%c_mod

    start=a+1
if end<n:
    end=n
    if (end-start) in cntmap:
        ans=ans*cntmap[end-start]%c_mod
    else:
        res=count(start,start,end)
        ans=ans*res%c_mod
print(ans)

Submission status: Time Limit Exceeded

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

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)
if al>0:
    a.sort()

f=0
for i in a:
    if i+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
for num in bl:
    l.remove(num)
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

n, m = map(int, input().split())
A = [0] * m
for i in range(m):
    A[i] = int(input())
B = []
if m > 1:
    for i in range(m - 1):
        if A[i + 1] - A[i] == 1:
            print(0)
            exit()
if m:
    B.append(A[0])
    A.append(n + 1)
    for i in range(len(A) - 2, -1, -1):
        B.append(A[i + 1] - A[i] - 1)
else:
    B.append(n + 1)
div = 1000000007
ans = 1
for b in B:
    if b < 3:
        continue
    c = b - 1
    two_max = c // 2
    a = 0
    for two in range(two_max + 1):
        one = c - (2 * two)
        a += factorial(one + two) // (factorial(one) * factorial(two))
    ans *= a
    ans %= div
print(ans)

Submission status: Time Limit Exceeded

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 and (i+1) not in a:
        hoge[i] = 1
    elif i == 1 and (i+1) not in a:
        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]
        hoge[i] = hoge[i] % (10**9 + 7)
print(hoge[N-1] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
af=0
for i in range(m):
    a.append(int(input()))
al=len(a)
if al>0:
    a.sort()
    af=1
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

Submission status: Time Limit Exceeded

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

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in enable_list:
  a[i] = a[i-1] + a[i-2]
  a[i] %= 1000000007

print(a[n])

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	Z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		Z[i][j] += X[i][k] * Y[k][j]
	return Z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		F = [[0, 1], [1, 1]]
	return mat2_pow(F, n - 1)[1][1] % INF


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a = list(set(a))
ans, start = 1, 0

for j in range(1, M):
	if a[j] - a[j - 1] == 1:
		print(0)
		exit()

for k in range(N):
	if k in a:
		ans *= fib(k - start)
		ans %= INF
		start = k + 1
ans *= fib(N - start + 1)
print(ans % INF)

Submission status: Time Limit Exceeded

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

memo = {
    0: 1
}
queue = [0]
counter = 0
def step(height, n):
    if height + n not in memo:
        memo[height + n] = memo[height]
    else:
        memo[height + n] += memo[height]
    if height + n not in queue:
        queue.append(height + n)


while counter < len(queue):
    # print(memo, queue, counter)
    item = queue[counter]
    counter += 1
    if item + 1 not in a and item + 1 <= N:
        step(item, 1)
    if item + 2 not in a and item + 2 <= N:
        step(item, 2)

if N not in memo:
    print(0)
else:
    print(memo[N] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#入力取得
from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
  if (n == 0):
    return (Fraction(1), Fraction(1));
  if (n % 2 == 0):
    return fibExp(fibMul(fn, fn), n / 2);
  return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
  a = fn1[0]
  b = fn1[1]
  c = fn2[0]
  d = fn2[1]
  return (a - c, b - d)

def fibMain(n):
  fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
  fibNum2 = (Fraction(1, 2), Fraction(-1, 2))

  fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n))
  fibNum4 = (Fraction(0, 1), Fraction(1, 5))
  return fibMul(fibNum3, fibNum4)

def fib(n):
  return fibMain(n)[0].numerator




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

a= []

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

l = ["1"] * (N + 1)

for a_ele in a:
    l[a_ele] = "0"

l = ''.join(l)

# print(l)

if '00' in l:
    print(0)

else:
    l_arr = l.split('0')
    result = 1
    for l_ele in l_arr:
        result *= fib(len(l_ele))

    result = result % 1000000007
    print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import sys
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]
m = 10**9+7
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

for i, a in enumerate(A[:-1]):
    if a+1 == A[i+1]:
        print(0)
        sys.exit()
ans = 1
s = 0
for i in range(N):
    if i in A:
        ans *= Fib(i-s+1)
        ans %= m
        s = i+1
ans *= Fib(N-s+2)
ans %= m 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [int(input()) for _ in range(M)]
k = 10**9+7
dp = [0]*(N+1)
dp[0] = 1
d = 1
if N == 1:
  print(1)
else:
  for i in range(1,N+1):
    if i in a:
      continue
    elif i==1:
      dp[i] = d
    elif i==2:
      d += dp[1]
      dp[i] = d
    else:
      d = d-dp[i-3]+dp[i-1]
      dp[i] = dp[i-1]+dp[i-2]
  print(dp[N]%k)

Submission status: Time Limit Exceeded

Solution code:
mod=1000000007
n,m=map(int,input().split())
a=[]
af=0
for i in range(m):
    a.append(int(input()))
if len(a)>0:
    a.sort()
    af=1
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if af==1 and len(a)>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)

Submission status: Time Limit Exceeded

Solution code:

import math


fact = {}


def calc(_n):
    _i = (_n - 1) // 2
    c = 0
    for j in range(_i+1):
        k1 = _n - 1 - j
        k2 = k1 - j
        if k1 not in fact:
            fact[k1] = math.factorial(k1)
        if j not in fact:
            fact[j] = math.factorial(j)
        if k2 not in fact:
            fact[k2] = math.factorial(k2)
        c += fact[k1] // (fact[j] * fact[k2])
    return c


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

b = 0
s = 1
for i in a:
    s *= calc(i-b)
    b = i + 1
if b != n:
    s *= calc(n+1-b)
print(s % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def func(n):
  if n==1:return 1
  if n==0:return 1
  if dp[n]!=-1:return dp[n]
  f1=func(n-1) if n-1 not in a else 0
  f2=func(n-2) if n-2 not in a else 0
  tmp=(f1+f2)%1000000007
  dp[n]=tmp
  return tmp
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
dp=[-1]*(n+1)
print(func(n)%1000000007)

Submission status: Time Limit Exceeded

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

case = [0] * (N + 1)
case[0] = 1
if not 1 in A:
    case[1] = 1
for x in range(2, N + 1):
    if x in A:
        case[x] = 0
    elif x - 1 in A:
        case[x] = case[x - 2]
    else:
        case[x] = case[x - 1] + case[x - 2]

print(case[N] % 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)]
x = 0
y = 1
for i in range(N):
  if i+1 in a:
    z = 0
  else:
    z = x + y
  x,y = y,z  
print(z%MOD)

Submission status: Time Limit Exceeded

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

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

memo = {}


def step(now):
    if now in a:
        return 0
    # print(now)
    if now == n:
        return 1
    if now > n:
        return 0
    if now in memo.keys():
        return memo[now]
    memo[now] = step(now+1)+step(now+2)
    return memo[now]


print(step(0) % 1000000007)
# print(memo)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
b = []
b.append(1) if a.count(1) == 0 else b.append(0)
b.append(b[0] + 1) if a.count(2) == 0 else b.append(0)

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

Submission status: Time Limit Exceeded

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

mod=1000000007

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

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

  dp[i+2] = dp[i+2] % mod
  #print(dp)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.special import perm
# from scipy.special import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

N, M = l_inpl()
a = [ i_inpl() for _ in range(M)]
# for _ in range(M):
#     ai = i_inpl()
#     a.append(ai)

dp = [None] * (N+1)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""


N, M = list(map(int, input().split()))
a = [0]*M
for m in range(M):
    a[m] = int(input())
MOD = 10**9 + 7

def main(): 
    dp = [0]*(N+2)
    dp[0] = 1
    for n in range(1,N+1):
        if n ==1:
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-1]
        else:                        
            if n in a:
                dp[n] = 0
            else:
                dp[n] += dp[n-2] + dp[n-1]
                
    #print(dp)
    print(dp[N]%MOD)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
A = [int(stdin.readline().rstrip()) for _ in range(M)]

def solve(n):
    dp = []
    for i in range(n+1):
        if i in A:
            dp.append(0)
        else:
            dp.append(1)
    for i in range(2, n+1):
        if dp[i] == 0:
            continue
        dp[i] = dp[i-1]+dp[i-2]
    return dp[n] % 1000000007

print(solve(N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

n,m=intinput()
a=[int(sys.stdin.readline()) for _ in range(m)]
memo=[0 for x in range(n+4)]
memo[0]=1
mod = 10**9+7
for i in range(n):
    if i+1 not in a:
        memo[i+1]=(memo[i+1]+memo[i])%mod
    if i+2 not in a:
        memo[i+2]=(memo[i+2]+memo[i])%mod
print(memo[n])

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
import collections
n, m = map(int, input().split())
dat_m = []
dp = collections.deque([])
for i in range(m):
    dat_m.append(int(input()))
dp.append(1)
for i in range(1, n + 1):
    t = 0
    t = dp[i - 1]
    if i > 1:
        t += dp[i - 2]
    if i in dat_m:
        t = 0
    t = t % mod
    dp.append(t)

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n) if i not in bl]
mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
from fractions import Fraction
import sys

from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
    a = fn1[0]
    b = fn1[1]
    c = fn2[0]
    d = fn2[1]
    return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
    if (n == 0):
        return (Fraction(1), Fraction(1));
    if (n % 2 == 0):
        return fibExp(fibMul(fn, fn), n / 2);
    return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
    a = fn1[0]
    b = fn1[1]
    c = fn2[0]
    d = fn2[1]
    return (a - c, b - d)

def fibMain(n):
    fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
    fibNum2 = (Fraction(1, 2), Fraction(-1, 2))
    fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n)) 
    fibNum4 = (Fraction(0, 1), Fraction(1, 5))
    return fibMul(fibNum3, fibNum4)

def fib(n):
    return fibMain(n)[0].numerator



n, m =map(int, input().split())  #複数数値入力
a = [-1]
for i in range(m):
    ai = int(input())
    a.append(ai)
a.append(n+1)

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:
#         y = 1/root5 *(((1+root5)/2)**x - ((1-root5)/2)**x) 
        count *= fib(x)
print(int(count)%1000000007)