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 math

N,M = map(int,input().split(' '))
An = [ int(input()) for _ in range(M)]

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

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += combinations_count(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)

all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        if all_sum > 10**9+7:
            all_sum = all_sum%(10**9+7)
        all_sum *= comb_count
print(all_sum%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

N,M = map(int,input().split(' '))
An = [ int(input()) for _ in range(M)]

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

def one_two_comb(N):
    two_n = N//2
    comb_list = []
    for i in range(1,two_n+1):
        comb_list.append([N-i,i])
    return comb_list

def sum_comb(comb_list):
    comb_sum = 0
    for val in comb_list:
        comb_sum += combinations_count(val[0],val[1])
    return comb_sum
    

diff_list = []
current_num = 0
for a in An:
    diff = a - current_num
    if diff == 0:
        print(0)
        exit(0)
    diff_list.append(diff)
    current_num = a +1
diff = N+1 - current_num
diff_list.append(diff)
#print(diff_list)

all_sum = 1
for idx,diff in enumerate(diff_list):
    if idx == 0 or len(diff_list):
        diff -= 1
    '''
    else:
        diff -= 2
    '''

    if diff == 0:
        all_sum *= 1
    else:
        internal_comb_list = one_two_comb(diff)
        comb_count = sum_comb(internal_comb_list) + 1
        all_sum *= comb_count
print(all_sum%(10**9+7))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m  = map(int, input().split())
broken_stairs = []
INF = 1000000007
for i in range(m):
    a = int(input())
    if i > 0:
        if a == broken_stairs[-1] + 1:
            print(0)
            quit()
    broken_stairs.append(a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

mod = 10 ** 9 + 7
n, m, *a = [int(x) for x in sys.stdin.read().split()]

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

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    p = [0, 1] # p[i] は連続するi段の、1~i段目までの登り方の総パターン
    for _ in range(n):
        p.append(p[-1] + p[-2])

    count = 1 # 最初に0th stepを踏んでいるので1
    sections = []
    for i in range(1, n+1):
        if i in safe:
            count += 1
        else:
            if count >= 1:
                sections.append(p[count])
                count = 0
            else: # countが0だったら一つ前も壊れている
                print(0)
                sys.exit()
    
    if count >= 1:    # if the last is not broken.
        sections.append(p[count])

    ans = reduce(lambda x, y: x * y % mod, sections)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    pattern_for_each_section = []
    ans = 1
    p = [0, 1]
    continuous_broken_count = 0
    for i in range(1, n+1):
        if i in safe:
            continuous_broken_count = 0
            p.append(p[-1] + p[-2])
        else:
            continuous_broken_count += 1
            if continuous_broken_count == 1:
                pattern_for_each_section.append(p[-1])
                p = [1, 0]
            else:
                print(0)
                sys.exit()
    
    if continuous_broken_count == 0:
        pattern_for_each_section.append(p[-1])
    

    for c in pattern_for_each_section:
        ans = ans * c % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    ans = 1
    p_pre_pre = 0
    p_pre = 1 # 0th step
    count = 0
    continuous_broken_count = 0
    for i in range(1, n+1):
        if i in safe:
            continuous_broken_count = 0
            count += 1
            if count % 2 == 1:
                p_pre_pre = p_pre + p_pre_pre
            else:
                p_pre = p_pre_pre + p_pre
        elif count != 0:
            continuous_broken_count = 1
            if count % 2 == 1:
                ans = ans * p_pre_pre % mod
            else:
                ans = ans * p_pre % mod
            p_pre_pre = 1
            p_pre = 0
            count = 0
        else:
            continuous_broken_count += 1
            if continuous_broken_count == 2:
                print(0)
                sys.exit()
            p_pre_pre = 1    
            p_pre = 0

    if count != 0:      # if n-th tread is not broken.
        if count % 2 == 1:
            ans = ans * p_pre_pre % mod
        else:
            ans = ans * p_pre % mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

mod = 10 ** 9 + 7
def main():
    n, m, *broken_treads = [int(x) for x in sys.stdin.read().split()]
    safe = sorted((set(range(1, n+1)) - set(broken_treads)))

    case = []
    p_pre_pre = 0
    p_pre = 1 # 0th step
    count = 0
    continuous_broken_count = 0
    for i in range(1, n+1):
        if i in safe:
            continuous_broken_count = 0
            count += 1
            if count % 2 == 1:
                p_pre_pre = p_pre + p_pre_pre
            else:
                p_pre = p_pre_pre + p_pre
        elif count != 0:
            continuous_broken_count = 1
            if count % 2 == 1:
                case.append(p_pre_pre)
            else:
                case.append(p_pre)
            p_pre_pre = 1
            p_pre = 0
            count = 0
        else:
            continuous_broken_count += 1
            if continuous_broken_count == 2:
                print(0)
                sys.exit()
            p_pre_pre = 1
            p_pre = 0

    if count != 0:      # if n-th tread is not broken.
        if count % 2 == 1:
            case.append(p_pre_pre)
        else:
            case.append(p_pre)

    ans = 1
    for c in case:
        ans = (ans * c) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(6, [3]), 4)

    def test_2(self):
        self.assertEqual(think(10, [4, 5]), 0)

    def test_3(self):
        self.assertEqual(think(100, [1, 23, 45, 67, 89]), 608200469)


def solve():
    n, a = read()
    result = think(n, a)
    write(result)


def read():
    n, m = read_int(2)
    a = [0 for x in range(m)]
    for i in range(m):
        a[i] = read_int(1)[0]
    return n, a


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, a):
    mode = 1000000007
    INVALID = -1

    ways = [0 for x in range(n + 1)]
    ways[0] = 1
    for e in a:
        ways[e] = INVALID

    for i in range(1, len(ways)):
        if i in a:
            continue
        if i >= 2:
            ways[i] += 0 if ways[i - 1] == INVALID else ways[i - 1]
            ways[i] += 0 if ways[i - 2] == INVALID else ways[i - 2]
            ways[i] %= mode
        else:
            ways[i] = 0 if ways[i - 1] == INVALID else ways[i - 1]
    return ways[-1]


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
import unittest


class TestC(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(6, [3]), 4)

    def test_2(self):
        self.assertEqual(think(10, [4, 5]), 0)

    def test_3(self):
        self.assertEqual(think(100, [1, 23, 45, 67, 89]), 608200469)


def solve():
    n, a = read()
    result = think(n, a)
    write(result)


def read():
    n, m = read_int(2)
    a = []
    for _ in range(m):
        a.append(read_int(1)[0])
    return n, a


def read_int(n):
    return read_type(int, n)


def read_float(n):
    return read_type(float, n)


def read_type(t, n):
    return list(map(lambda x: t(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n, a):
    mode = 1000000007
    ways = [0 for x in range(n + 1)]
    ways[0] = 1
    for i in range(1, len(ways)):
        if i in a:
            ways[i] = 0
            continue
        if i >= 2:
            ways[i] = ways[i - 1] + ways[i - 2]
            ways[i] %= mode
        else:
            ways[i] = ways[i - 1]
    return ways[-1]


def write(result):
    print(result)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

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

MOD = 1000000007
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]) % MOD
            
print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/abc129/tasks/abc129_c

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

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

main()

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

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

print(dp[0])

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

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

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N , M = map(int, input().split())
a = list()
for n in range(M):
    a.append(int(input()))
dp = np.zeros(N+1)
dp[0] = 1
if M == 0:
    dp[1] = 1
else:
    dp[1] = 0 if a[0] == 1 else 1
for n in range(2,N+1):
    if n in a:
        dp[n] = 0
    else:
        dp[n] = (dp[n-1]+dp[n-2])%(10**9+7)
print(int(dp[N]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
inf = float("inf")
dp = [inf] * (N+1)
dp[0] = 1
for i in range(1,N+1):
	if i in A:
		continue

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

	a = dp[i-2] if dp[i-2] != inf else 0
	b = dp[i-1] if dp[i-1] != inf else 0

	dp[i] = (a + b) % 1000000007


print(dp[N])

Submission status: Time Limit Exceeded

Solution code:
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
   
fib = [0] * (N + 1)
if 1 in break_list:
    fib[1] = 0
else:
    fib[1] = 1
    
fib[0] = 1
for i in range(N - 1):
    if i + 2 in break_list:
        fib[i + 2] = 0
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = ( end - start ) // 2 
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) ) 
    ans *= sum_c
    start = i + 1
    
if i > -1:
    print( ans % 1000000007 )
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) ) 
    ans *= sum_c
    start = i + 1
    
if i > -1:
    print( ans % 1000000007 )
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k+j) // ( fac(k) * fac(j) )
    ans *= sum_c
    start = i + 1
    
if i >= 0:
    print( ans % 1000000007 )
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
from bisect import bisect_left
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    ind = bisect_left(A, n)
    if ind < M and n == A[ind]:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

Submission status: Time Limit Exceeded

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

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

Submission status: Time Limit Exceeded

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

from functools import lru_cache
@lru_cache(maxsize=None)
def fibo(n):
    if n in A:
        return 0
    elif n == 0 or n == 1:
        return 1
    return fibo(n-2) + fibo(n-1)

print(fibo(N) % 1000000007)

Submission status: Time Limit Exceeded

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

NL=[0]*(n+1)
NL[0],NL[1]=1,1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7
  
if not 1 in a:
  b[1]=1
  
for j in range(2,n+1):
  if not j in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n])

Submission status: Time Limit Exceeded

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

b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7
  
if 1 not in a:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n])

Submission status: Time Limit Exceeded

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

b=[0]*(n+1)
b[0]=1
MOD=(10**9)+7
  
if 1 not in a:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=b[j-1]+b[j-2]
    
print(b[n]%MOD)

Submission status: Time Limit Exceeded

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

for i in range(0,m):
  a.append(int(input()))
  
if 1 not in a:
  b[1]=1
  
for j in range(2,n+1):
  if j not in a:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)

Submission status: Time Limit Exceeded

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

for i in range(0,m):
  a.append(int(input()))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j in a:
    continue
  else:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

t=list(map(int, input().split()))
N=int(t[0])
M=int(t[1])
a=[-1]
for i in range(M):
        a.append(int(input()))
a.append(N+1)
d=1
for i in range(M+1):
        b=a[i+1]-a[i]-1
        c=0
        if (b==0):c=0
        else:
                for j in range(int((b-1)/2)+1):
                        c = c + int(comb((b-1-j),j))
                        c = c%1000000007
        d = d*c
        d = d%1000000007
print(d)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
t=list(map(int, input().split()))
N=int(t[0])
M=int(t[1])
a=[-1]
for i in range(M):
        a.append(int(input()))
a.append(N+1)
d=1
for i in range(M+1):
        b=a[i+1]-a[i]-1
        c=0
        if (b==0):c=0
        else:
                for j in range(int((b-1)/2)+1):
                        c = c + int(comb((b-1-j),j))
                        c = c%1000000007
        d = d*c
        d = d%1000000007
print(d)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  n,m=map(int,input().split())
  broken=[0]*m
  for i in range(m):
    broken[i]=int(input())
  
  dp=[0]*(n+1)
  dp[0]=1
  dp[1]=1 if 1 not in broken else 0

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

solve()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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
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[-1] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def xgcd(a, b):
    if b == 0:
        g = a
        x = 1
        y = 0
        return g, x, y
    else:
        g, s, t = xgcd(b, a%b)
        x = t
        y = s - a//b*x
        return g, x, y

def invmod(a, p):
    _, x, _ = xgcd(a, p)
    if x < 0:
        x = x + p
    return x

def count_route(n):
  if n < 0:
    return 0
  res = 0
  for i in range(n//2+1):
    res += f[n - i] * inv[i] * inv[n - 2* i]
  return res%const
    
n, m = map(int, input().split())
const = 1000000007
#nまでの階乗をハッシュテーブルに格納する
f = [1 for i in range(n + 1)]
inv = [1 for i in range(n + 1)]
for i in range(1, n+1):
  f[i] = f[i - 1] * i
  inv[i] = invmod(f[i], const)
prev = 0
ans = 1
for i in range(m):
  m = int(input())
  ans = (ans * count_route(m - 1 - prev))%const
  prev = m + 1
  if ans == 0:
    break
ans = (ans * count_route(n - prev))%const
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 1000000007  # type: int

def solve(N: int, M: int, a: "List[int]"):
    dp = [0] *(N+2)
    ckc = [True] * (N+2)
    for i in a:
        ckc[i] = False

    def f(n: int):
        if(dp[n] != 0):
            return dp[n]

        if n <= 0:
            dp[n] = 0
        else:
            if not ckc[n-1] and not ckc[n-2]:
                dp[n] = 0
            elif not ckc[n-1]:
                dp[n] = f(n-2) % MOD
            elif not ckc[n-2]:
                dp[n] = f(n-1) % MOD
            else:
                dp[n] = (f(n-1) + f(n-2)) % MOD
            
        return dp[n]

    dp[0] = 1
    f(N)
    print(dp[N])
    # print(dp)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    ansls = [0]*(n+1)

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    ansls = [0]*(n+1)

    if 0 not in a:
        ansls[0] = 1
    if 1 not in a:
        ansls[1] = 1

    for i in range(2, n+1):
        if i not in a:
            ansls[i] = (ansls[i-2] + ansls[i-1])%(10**9 + 7)
    
    print(ansls[-1])
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
big=10**9+7

def modsum(a,b):
  return a%big +b%big

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

a = [0]*m
for i in range(m):
  a[i] = int(input())
  
#連続こわれ
for i in range(m-1):
  if a[i]+1 == a[i+1]:
    print(0)
    sys.exit(0)

cho = [0]*(n+1)
if 0 not in a:
  cho[0] = 1
if 1 not in a:
  cho[1] = 1

for i in range(2,n+1):
  if i not in a:
    cho[i] = modsum(cho[i-1], cho[i-2])


print(cho[-1]%big)

Submission status: Time Limit Exceeded

Solution code:
import sys
big=10**9+7

def modsum(a,b):
  return a%big + b%big

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

a = [0]*m
for i in range(m):
  a[i] = int(input())
  
#連続こわれ
for i in range(m-1):
  if a[i]+1 == a[i+1]:
    print(0)
    sys.exit(0)

#選択肢計算
cho = [1]*n
if 1 in a:
  cho[1]=0

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


print(cho[-1]%big)

Submission status: Time Limit Exceeded

Solution code:
def stairs(n,a):
    var1 = 1
    var2 = 1
    tmp = 1
    if 1 in a:
        var2 = 0
    for i in range(1,n):
        if i+1 in a:
            tmp = 0
            var1 = var2
            var2 = tmp
        else:    
            tmp = var1 + var2
            var1 = var2
            var2 = tmp
    return tmp

N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
             
a = stairs(N,A)
print(a%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

if m != 0:
    lin = [int(stdin.readline().rstrip()) for _ in range(m)]
else:
    lin = [-1]

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

if lin[0] == 1:
    dp[1] = 0
else:
    dp[1] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

if m != 0:
    lin = [int(stdin.readline().rstrip()) for _ in range(m)]
else:
    lin = [-1]

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

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

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

Submission status: Time Limit Exceeded

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

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

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

print(dp[n])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

print(result[n])

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

print(result[n])