Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq M \leq N-1

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

Input

Input is given from Standard Input in the following format:

N M
a_1
a_2
 .
 .
 .
a_M

Output

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

Sample Input 1

6 1
3

Sample Output 1

4

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

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

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

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

0 \to 2 \to 4 \to 6

Sample Input 2

10 2
4
5

Sample Output 2

0

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

Sample Input 3

100 5
1
23
45
67
89

Sample Output 3

608200469

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



Sample input:
6 1
3


Sample output:
4

Submission status: Wrong Answer

Solution code:
p = [0]*100001
p[0] = 1
p[1] = 1
p[2] = 2
ans = 1
for i in range(3,100001):
	p[i] = p[i-1] + p[i-2]


n,m = map(int,input().split())
l = [0]*(m+2)
l[m+1] = n
for i in range(m):
	l[i+1] = int(input())

l1 = [0]*(m+1)
for i in range(m+1):
	l1[i] = l[i+1] - l[i]

if m == 0:
	print(p[n])
else:
	for i in range(m+1):
		if i == 0 or i == m:
			ans = ans * p[l1[i]-1]
		else:
			if l1[i] == 1:
				print(0)
				break
			else:
				ans = ans * p[l1[i]-2]

print(ans)

Submission status: Wrong Answer

Solution code:
fib=[0,1]
for i in range(9999):
  fib.append(fib[-1]+fib[-2])
  
n,m=map(int,input().split())
hoge=[]
ans=1
for i in range(m):
  hoge.append(int(input()))
hoge.append(n+1)

for i in range(len(hoge)-1):
  if(hoge[i+1]-hoge[i]==1):
    print(0)
    exit()
    
  ans=ans*max(1,fib[hoge[i+1]-hoge[i]-1])
  ans=ans%1000000007
  
print(ans%1000000007)

Submission status: Wrong Answer

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

combination = [1,1,2]
for i in range(3,N):
    combination.append(combination[i-1]+combination[i-2])

a = 0
ans = 1
lst = []
for i in range(M):
    next_a = int(input())
    if next_a == 1:
        lst.append(1)
        a = next_a
        continue
    elif next_a-a == 1:
        ans = 0
        break
    lst.append(combination[next_a-a-2])
    a = next_a
next_a = N
lst.append(combination[next_a-a-1])

for tmp in lst:
    ans *= tmp
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# IMPORT ###############################################################################################################
import sys                                                      # システム
sys.setrecursionlimit(10**6)                                    # 再帰処理の上限変更
from collections import deque, Counter                          # キュー・個数カウント
from itertools   import accumulate, permutations, combinations  # 累積和・順列・組み合わせ
from operator    import itemgetter                              # ソート補助
from bisect      import bisect_left, bisect_right, bisect       # 二分探索
from heapq       import heappop, heappush                       # プライオリティキュー
from fractions   import gcd                                     # 最大公約数
from math        import ceil, floor, sqrt, cos, sin, tan, pi    # 数学処理
from copy        import deepcopy                                # オブジェクトコピー
import numpy         as np                                      # 数値計算

# MAIN #################################################################################################################
def main():
    # Init #############################################################################################################
    im = InputManager()
    # Input ############################################################################################################
    n, m = im.inputMultiple()
    a = im.input2D(h=m)
    MOD = 1000000007
    # Logic ############################################################################################################
    idx = 0
    total = 1
    fib = fibonacci(n)
    for ai in a:
        ai = ai[0]
        if (ai - idx) == 1 and idx != 0:
            print(0)
            return
        total *= fib[ai - idx - 1]
        idx = ai+1
    total *= fib[n - idx]
    # Output ###########################################################################################################
    print(total % MOD)
    # Return ###########################################################################################################
    return

def fibonacci(n):
    fib = [1, 1]
    for _ in range(n - 1):
        fn_1 = fib[len(fib)-1]
        fn_2 = fib[len(fib) - 2]
        fib.append(fn_2 + fn_1)
    return fib

# INPUT MANAGER ########################################################################################################
class InputManager(object):
    def __init__(self):
        pass

    @staticmethod
    def inputSingle(dtype=int):
        return dtype(input())
    
    @staticmethod
    def inputMultiple(dtype=int, aslist=False):
        if aslist:
            return list(map(dtype, input().split()))
        else:
            return map(dtype, input().split())

    @staticmethod
    def input2D(h, dtype=int):
        return [list(map(dtype, input().split())) for i in range(h)]

# CALL MAIN ############################################################################################################
main()

Submission status: Wrong Answer

Solution code:
def fib(number):
    if(number<=2):
        return 1
    else:
        f = 1
        ff = 1
        for _ in range(number-1):
            tmp = ff
            ff = f + ff
            f = tmp
        return tmp

n, m = map(int, input().split())
a = []

frag = True
before = -100
for _ in range(m):
    tmp = int(input())
    if(tmp - before == 1):
        frag = False
    before = tmp
    a.append(tmp)


warukazu = 1000000007
if(frag):
    before = 0
    ans = 0
    for i in range(m):
        if(i==0):
            ans = fib(a[i]-before)
        else:
            ans = ans * fib(a[i]-before-1)
            ans = ans % warukazu
        before = a[i]
    ans = ans * fib(n - before)
    ans = ans % warukazu
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
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


def main():
    N, M = map(int, input().split())  # 複数数値入力
    li = list()
    last = -1
    current = N
    ans = 1
    beforeBroken = 0
    for i in range(M):
        current = int(input())
        beforeBroken = current
        if last == current - 1 and last != 0:
            print(0)
            return

        if current != 1:
            li.append(current - last-2)
        last = current

    li.append(N - beforeBroken-1)

    for i in li:
        ans *= Fib(i+2)
    print(ans % 1000000007)


main()

Submission status: Wrong Answer

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

if 1 in a and 2 in a:
  print(0)
else:
  i1 = 0
  i2 = 1
  i3 = 0
  for i in range(1, N+1): #インデックスは-1
    if i in a:
      i1 = i2
      i2 = i3
      i3 = 0
    else:
      i3 = i1 + i2
      i1 = i2
      i2 = i3
      i3 = 0
  
  print(i3%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
s=n-len(a)*2
S=[1,2]
for i in range(s):
    S.append((S[-1]+S[-2])%1000000007)
print(S)
step=[]
a=[0]+a+[n]
for i in range(len(a)-1):
    if i==0 and a[1]==1:
        step.append(1)
    elif i==0:
        step.append(S[a[i+1]-a[i]-2])
    elif i==len(a)-2 and a[-1]==n-1:
        step.append(1)
    elif i==len(a)-2:
        step.append(S[a[i+1]-a[i]-2])
    elif a[i+1]-a[i]==1:
        print(0)
        sys.exit()
    else:
        step.append(S[a[i+1]-a[i]-3])
print(step)
ans=1
for i in step:
    ans*=i
    ans%=1000000007
print(ans)

Submission status: Wrong Answer

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

t = 1000000007
ans = 1


def Fib(n):
    a, b = 1, 2
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n - 2):
            a, b = b, a + b
        return b


if m == 1:
    ans = ans * Fib(a[0] - 1) * Fib(n - a[0] - 1)
else:
    for i in range(m):
        # 最初の段
        if i == 0:
            ans = ans * Fib(a[i] - 1)
        # 二段壊れは0
        elif a[i] - a[i - 1] == 1:
            ans = 0
            break
        # 最後の段
        elif i == m - 1:
            if a[i] != n - 1:
                ans = ans * Fib(n - a[i] - 1)
                break
            else:
                break
        # 壊れ段の間
        else:
            ans = ans * Fib(a[i] - a[i - 1] - 2)

print(ans % t)

Submission status: Wrong Answer

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

li = [0]*10**6
lia = [-1]
ans = 1
mod = 1000000007

for i in range(n):
    if i == 0:
        li[i] = 1
    elif i == 1:
        li[i] = 1
    else:
        li[i] = li[i-1] + li[i-2]

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

lia.append(n+1)

for i in range(len(lia)-1):
    if lia[i+1]-lia[i] != 1:
        ans *= li[lia[i+1]-lia[i]-2]
    else:
        ans = 0
    ans %= mod

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
p = []
pre = 0

def pattern_count(a,b):
    if a == 0 or b == 0:
        return 1
    else:
        return math.factorial(a+b)//(math.factorial(a)*math.factorial(b))

def count(a):
    ret = 0
    for i in range(a//2 + 1):
        ret += pattern_count(i, a-i*2)
    if ret == 0:
        return 1
    else:
        return ret

fault = False
for _ in range(m):
    a = int(input())
    if a == pre:
        fault = True
        break
    print(a-pre-1)
    p.append(count(a-pre-1))
    pre = a+1

if fault:
    print(0)
else:
    p.append(count(n-pre))

    ans = 1
    for a in p:
        ans *= a

    print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import math
n, m = map(int, input().split())
p = []
pre = 0

def pattern_count(a,b):
    if a == 0 or b == 0:
        return 1
    else:
        return math.factorial(a+b)//(math.factorial(a)*math.factorial(b))

def count(a):
    ret = 0
    for i in range(a//2 + 1):
        ret += pattern_count(i, a-i*2)
    if ret == 0:
        return 1
    else:
        return ret

fault = False
for _ in range(m):
    a = int(input())
    if a == pre:
        fault = True
        break
    print(a-pre-1)
    p.append(count(a-pre-1))
    pre = a+1

if fault:
    print(0)
else:
    p.append(count(n-pre))

    ans = 1
    for a in p:
        ans *= a

    print(p)
    print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
N_M = list(map(int, input().split()))
N = N_M[0]
M = N_M[1]
dis = []
for _ in range(M):
    dis.append(input())

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

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

print(dp[N])

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

n, m = map(int, input().split())
a = [0] * (n + 1)

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

l = [0] * (n + 1)
l[n] = 1
l[n-1] = 1
if a[n-1] == 1:
    l[n-1] = 0

num = n - 2
while num >= 0:
    if a[num] == 0:
        l[num] = (l[num+1] % mod) + (l[num+2] % mod)
    else:
        l[num] = 0
    num -= 1

print(l[0])

Submission status: Wrong Answer

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

print(fib(100))



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)

Submission status: Wrong Answer

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]
print(enable_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]

print(a[n]%1000000007)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
a=[]
for i in range(m):
    a.append(int(input()))
memo=[0]*100001
memo[1]=1
memo[2]=2
for i in range(3,100001):
    memo[i]=memo[i-1]+memo[i-2]

ans=1
pre=-1
for i in a:
    if i==1:
        pre=1
        continue
    if pre==(i-1):
        print(0)
        exit()
    if i==2:
        pre=2
        continue
    ans*=memo[i-pre-2]
    pre=i
ans*=memo[n-pre-1]
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
hoge[0] = 1
for i in range(N):
    if i == 0 and (i+1) not in a:
        hoge[i] = 1
    elif i == 1 and (i+2) 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: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = [1]+[2]+[0]*100000

for i in range(2, 100002):
    F[i] = F[i-1] + F[i-2]

ans = 1
cur = 0
for i in range(M):
    broken = int(input())
    if cur == broken:
        print(0)
        break
    elif broken - cur == 1:
        cur = broken + 1
    else:
        ans *= F[broken - cur - 2]
        ans %= 1000000007
        cur = broken + 1
else:
    ans *= F[N - cur - 1]
    print(ans % 1000000007)

Submission status: Wrong Answer

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

tmp = [1, 2]
for i in range(10 ** 5):
    tmp.append(tmp[-1] + tmp[-2])

ans = 1
before = -1
for i in range(m):
    step = (a[i] - 1) - before - 1
    if step < 0:
        ans = 0
        break
    elif step > 0:
        ans = ans * tmp[step-1]
        ans = ans % 1000000007

    before = a[i]

# final steps
step = n - before - 1
if step == 0:
    ans = 0
elif step > 0:
    ans *= tmp[step-1]
    ans = ans % 1000000007

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
list = [0] * n
list[0] = 1
if n >= 2:
    list[1] = 2
if n >= 3:
    for i in range(2, n):
        list[i] = list[i - 2] + list[i - 1]

if m == 0:
    print(list[n - 1])
else:
    ans = 1
    o = 0
    for i in range(m):
        a = int(input())
        if a == o:
            ans = 0
            break
        if a > o + 1:
            ans = (ans * list[a - o - 2]) % 1000000007
        o = a + 1

    if a + 1 < n:
        ans = (ans * list[n - a - 2]) % 1000000007
    print(ans)

Submission status: Wrong Answer

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

C = [0]*(N+1)
C[0]=1
for i in range(N-1):
    C[i+1]+=(C[i]*D[i])%MOD
    C[i+2]+=(C[i]*D[i])%MOD
C[N]+=(C[N-1]*D[N-1])%MOD
    #print(C)
print(C[N])

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

n, m = map(int, input().split())
a = [0] * (n + 1)

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

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

num = n - 2
while num >= 0:
    if a[num] == 0:
        l[num] = (l[num+1] % mod) + (l[num+2] % mod)
    else:
        l[num] = 0
    num -= 1

print(l[0])

Submission status: Wrong Answer

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

B = ['.'] * (N + 1) + ['#']
for a in A:
    B[a] = '#'
    
ans = 1
for i in range(N):
    if B[i] == '.':
        tmp = 0
        if B[i + 1] == '.':
            tmp += 1
        if B[i + 2] == '.':
            tmp += 1
        ans *= tmp
        ans %= mod
    
print(ans % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
a=[]
for i in range(m):
    a.append(int(input()))
memo=[0]*100001
memo[1]=1
memo[2]=2
for i in range(3,100001):
    memo[i]=memo[i-1]+memo[i-2]
#残り段数→通り
def step(rem):
    if memo[rem]!=0:
        return memo[rem]
    else:
        return step(rem-1)+step(rem-2)

ans=1
pre=0
for i in a:
    if i==1:
        pre=1
        continue
    if pre==(i-1) and pre!=0:
        print(0)
        exit()
    if i==2:
        pre=2
        continue
    ans*=step(i-pre-2)
    pre=i
ans*=step(n-pre-1)
print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = [1]+[2]+[0]*100000

for i in range(2, 100002):
    F[i] = F[i-1] + F[i-2]

ans = 1
cur = 0
for i in range(M):
    broken = int(input())
    if cur == broken:
        print(0)
        break
    elif broken - cur == 1:
        cur = broken + 1
    else:
        ans *= F[broken - cur - 2]
        cur = broken + 1
else:
    ans *= F[N - cur - 1]
    print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
N_M = list(map(int, input().split()))
N = N_M[0]
M = N_M[1]
dis = []
for _ in range(M):
    dis.append(input())

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0
    else:
        if i in dis :
            dp[i+2]=dp[i+1]
        if i+1 in dis :
            dp[i+2]=dp[i]
        else :
            dp[i+2]=dp[i]+dp[i+1]

print(dp[N])

Submission status: Wrong Answer

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

tmp = [1, 2]
for i in range(10 ** 5):
    tmp.append(tmp[-1] + tmp[-2])

ans = 1
before = -1
for i in range(m):
    step = (a[i] - 1) - before - 1
    if step < 0:
        ans = 0
        break
    elif step > 0:
        ans = ans * tmp[step-1]
        ans = ans % 1000000007

    before = a[i]

# final steps
step = n - before - 1
ans *= tmp[step-1]
ans = ans % 1000000007

print(ans)

Submission status: Wrong Answer

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

if M == 0:
    A = [-1]
else:
    A = [-1] * M
    for i in range(M):
        A[i] = int(input())
A = set(A)

root = [0] * (N+1)  # N danme madeno root
root[0] = 1  # start is 1

if N == 1:
    if 1 in A:
        print(0)
    else:
        print(1)
    exit()

if N == 2:
    if 1 in A and 2 in A:
        print(0)
    else:
        if 1 in A:
            print(1)
        else:
            print(0)
    exit()

root[1] = 0 if 1 in A else 1
root[2] = 0 if 2 in A else (root[0] + root[1])

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

print(root[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

n, m = map(int, input().split())
a = [0] * (n + 1)

for i in range(m):
    tmp_a = int(input())
    a[tmp_a] = 1

l = [0] * (n + 1)

l[n] = 1
l[n-1] = 1

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

print(l[0])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M  = map(int, input().split())
A = {}
mod = 10**9+7
for i in range(M):
    a = int(input())
    A[a] = 1
    if a-1 in A:
        print(0, '_', i)
        exit()

stairs = [0 for _ in range(N+2)]
stairs[0] = 1

for i in range(N):
    if i+1 not in A:
        stairs[i+1] = (stairs[i] + stairs[i+1]) % mod
    if i+2 not in A:
        stairs[i+2] = (stairs[i] + stairs[i+2]) % mod
        
print(stairs[N])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import bisect

MOD = 1000000007  # type: int

def is_ok(i,a):
    ii = bisect.bisect_left(a,i)
    if ii >= len(a):
        return True
    return i != a[ii]


def solve(N: int, M: int, a: "List[int]"):
    ppc = 1 if is_ok(1,a) else 0

    pc = 0
    if is_ok(2,a):
        if is_ok(1,a):
            pc = 2
        else:
            pc = 1

    c = 0
    for i in range(2,N):
        if is_ok(i+1,a):
            c = ppc + pc
        else:
            c = 0
        ppc,pc = pc,c

    print(c % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]
b = []
ans, mod = 1, 10**9+7
for i in range(m+1):
    b.append(a[i+1]-a[i]-1)
print(b)
for i in range(m+1):
    diff = b[i]
    dp = [1, 1]
    if i != 0 and diff == 0:
        print(0)
        exit()
    for j in range(diff-2):
        dp.append(dp[j]+dp[j+1])
    ans *= dp[-1]
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lis = [int(input()) for i in range(m)]
dp = [0 for i in range(n+2)]
lis.append(0)
dp[0] = 1
cou = 0
co = 0
for i in range(n):
  if i+1 != lis[cou]:
    dp[i+1] += dp[i]
    dp[i+1] %= 10 ** 9+7
  else:
    cou +=1
  if i+2 != lis[co]:
    dp[i+2] += dp[i]
    dp[i+2] %= 10 ** 9 + 7
  else:
    co += 1
print(dp[n])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
a={int(input()) for _ in range(M)}
print(a)

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

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

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

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

n, m = map(int, input().split())
a = [0] * (n + 1)

pre_a = -1
flag = True
for i in range(m):
    tmp_a = int(input())
    if pre_a + 1 == tmp_a:
        flag = False
    a[tmp_a] = 1
    pre_a = tmp_a

l = [0] * (n + 1)

l[n] = 1
l[n-1] = 1

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

if flag:
    print(l[0])
else:
    print(0)

Submission status: Wrong Answer

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

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

stairs[1] = 1
for i in a:
    stairs[i] = -100


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


print(stairs[n] % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
a = [int(input()) for i in range(M)]
hoge = [0] * N
hoge[0] = 1
for i in range(N):
    if i == 0 and (i+1) not in a:
        hoge[i] = 1
    elif i == 1 and (i+2) 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]
print(hoge[N-1] % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [0]*(N + 1)
dp[0] = 1
for step in range(N):
    if not step in a:
        for width in [1, 2]:
            to = step + width
            if to <= N and not to in a:
                dp[to] = (dp[to] + dp[step]) % MOD

print(dp[N])

Submission status: Wrong Answer

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

print(a)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def SI(): return input()


MOD = 1000000007


def comb(a, b):
    ans = 1
    for i in range(1, min(a-b, b)+1):
        ans *= a - i + 1
        ans //= i
        ans = ans % MOD
    return ans


def calc(N):
    r = 1
    for b in range(N//2):
        a = N - b*2
        r += comb(a+b, b)
        r %= MOD
    return r


def main():
    N, M = LI()
    now = 0
    ans = 1
    for _ in range(M):
        a = int(input())
        if a == now-1:
            continue
        if a == now:
            print(0)
            return
        ans = (ans*calc(a-now-1)) % MOD
        now = a+1
    ans = (ans*calc(N-now)) % MOD
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * M

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

A = set(A)
root = [0] * (N+1)  # N danme madeno root
root[0] = 1

if N == 1:
    if 1 in A:
        print(0)
    else:
        print(1)
    exit()

if N == 2:
    if 1 in A and 2 in A:
        print(0)
    else:
        if 1 in A:
            print(1)
        else:
            print(0)
    exit()

if 1 in A:
    root[1] = 0
else:
    root[1] = 1

if 2 in A:
    root[2] = 0
else:
    root[2] = root[0] + root[1]

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

print(root[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))

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

Submission status: Wrong Answer

Solution code:
MOD = 1000000007


def main():
    n, m = map(int, input().split())
    aa = set(int(input()) for _ in range(m))
    ss = [0 for _ in range(n + 1)]
    ss[0] = 1
    if not 1 in aa:
        ss[1] = 1
    for i in range(1, n + 1):
        if i in aa:
            continue
        ss[i] = (ss[i - 1] + ss[i - 2]) % MOD
    print(ss[n])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if 1 in a and 2 in a:
  print(0)
else:
  if 1 in a:
    k = [0, 1]
  elif 2 in a:
    k = [1, 0]
  else:
    k = [1, 2]
    
  for i in range(3, N+1): #インデックスは-1
    if i in a:
      k.append(0)
    else:
      k.append(k[i-3]+k[i-2])
      
  print(k[-1]%1000000007)