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:
n, m = list(map(int, input().split()))
aaa = list(int(input()) for i in range(m))

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

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

Submission status: Wrong Answer

Solution code:
# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = set([int(input()) for i in range(M)])
    inf = 10**9+7

    #動的計画法問題
    dp = [0] * (N+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1
    else:
        dp[1] = 0

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

    print(dp[N]) 

     
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Wrong Answer

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

dp = [0 if i in li else 1 for i in range(n+1)]

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

Submission status: Wrong Answer

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


def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for _ in range(M)] + [N+1]
    for i in range(1, M):
        if A[i+1] - A[i] == 1:
            print(0)
            exit()
    ans = 1
    mod = 10 ** 9 + 7
    comb_dict = {}
    for i in range(M+1):
        d = A[i+1] - A[i] - 2
        if d <= 0:
            continue
        if d not in comb_dict:
            comb_sum = 0
            for freq_of_2 in range((d // 2) + 1):
                freq_of_1 = d - 2 * freq_of_2
                comb_sum += int(math.factorial(freq_of_2 + freq_of_1) / (math.factorial(freq_of_1) * math.factorial(freq_of_2)))
            comb_dict[d] = comb_sum
        ans = (ans * comb_dict[d]) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def main():
    N, M = map(int, input().split())
    A = [-1] + [int(input()) for _ in range(M)] + [N+1]
    for i in range(1, M):
        if A[i+1] - A[i] == 1:
            print(0)
            exit()
    ans = 1
    mod = 10 ** 9 + 7
    for i in range(M+1):
        d = A[i+1] - A[i] - 2
        if d <= 0:
            continue
        comb_sum = 0
        for freq_of_2 in range((d // 2) + 1):
            freq_of_1 = d - 2 * freq_of_2
            comb_sum += int(math.factorial(freq_of_2 + freq_of_1) / (math.factorial(freq_of_1) * math.factorial(freq_of_2)))
        ans = (ans * comb_sum) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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



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

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

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
b = list(int(input()) for i in range(a[1]))
a0=1
a1=1
a2=0
for i in range(2,a[0]+1):
  if i-2 in b:
    a0 = 0
  if i-1 in b:
    a1 = 0
  a2 = a1 + a0
  a0 = a1
  a1 = a2
print(a2%(10**9+7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())

memo = defaultdict(int)

def dfs(now):

    if now == N-2:
        return 2

    if now == N-1:
        return 1

    if now == N:
        return 1

    if not memo[now+1]:
        memo[now+1] = dfs(now+1)

    if not memo[now+2]:
        memo[now+2] = dfs(now+2)

    return memo[now+1] + memo[now+2]

memo[0] = dfs(0)

fibo = [0] * (N+1)
fibo[0] = 1
fibo[1] = 1
for i in range(2, N+1):
    fibo[i] = fibo[i-1] + fibo[i-2]

tmp = 0
ans = memo[0]
for i in range(M):
    a = int(input())
    ans -= memo[a] * (fibo[a] - tmp)
    tmp += fibo[a]

print(ans % (10**9+7))

Submission status: Wrong Answer

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

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

dp[0] = 1


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

Submission status: Wrong Answer

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

mod = 10**9+7
dp = [-1]*(n+1)
dp[0]= 1
for i in range(m):
    a = int(input())
    dp[a-1] = 0
#print(dp)
#dp[1] = 1
#dp[2] = 2
for i in range(1,n+1):
    if i <= 1:
        dp[i] = dp[i-1]+1
    elif i>=2 :
        dp[i] = (dp[i-1]+ dp[i-2])%mod
        #print(dp)
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
L =  [] 
for i in range(m):
    L.append(int(input()))
print(L)
mod = 10**9+7
dp = [0]*(n+1)
dp[0]= 1
dp[1] = 1
#dp[2] = 2
for i in range(1,n+1):
    if 1 in L:
        dp[1] = 0
    if i in L:
        continue
    else:
        if i <= 1:
            dp[i] = dp[i-1]
        elif i>=2 :
            dp[i] = dp[i-1]+ dp[i-2]
        #print(dp)
print(dp[n]%mod)

Submission status: Wrong Answer

Solution code:

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
dp = [1]*(n+2) 

mod = 10**9 + 7
for i in range(m):
    a = int(input())
    dp[a-1] = 0

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

print(dp[n-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
stair=[0]*(n+1)
for i in range(m):
    s=list(map(int,input().split()))
    stair[s[0]]=-1
stair[-1]=1
stair[-2]=1
for i in range(n-2,-1,-1):
    if stair[i]==-1:continue
    elif stair[i+1]==-1:stair[i]=stair[i+2]
    elif stair[i+2]==-1:stair[i]=stair[i+1]
    else:stair[i]=stair[i+1]+stair[i+2]
print(stair)

Submission status: Wrong Answer

Solution code:
n,m,*L = map(int,open(0).read().split())
mod = 10**9+7

dp = [0]*(n+1)
if 1 in L:
    dp[0] = 0
    dp[1] = 1
elif 1 not in L:
    dp[0] = 1
    dp[1] = 2

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

Submission status: Wrong Answer

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

a_lst = []
case = [0] * n
for j in range(m):
  a = int(input())
  a_lst.append(a)

for k in range(n):
  if (k + 1) in a_lst:
    pass
  elif k == 0:
    case[k] = 1
  elif k == 1:
    case[k] = case[k-1] + 1
  else:
    case[k] = case[k-1] + case[k-2]
print(case[-1])

Submission status: Wrong Answer

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

for i in a:
    stp[i-1]=0

cnt=1

for i in range(n):
    if stp[i]==stp[i-1]:
        cnt*=0

if stp[0]!=0:
    cnt*=2

for i in range(2,n):
     if stp[i]!=0 and stp[i-1]!=0 and stp[i-2]!=0:
         cnt*=2

if cnt==0:
    print('0')
else:
    ans=cnt%1000000007
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
stairs = [0]*(n+1)
for _ in range(m):
    a = int(input())
    stairs[a] = 1
mod = 10**9 + 7

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

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

print(dp[n]%mod)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
stairs = [0]*(n+1)
for _ in range(m):
    a = int(input())
    stairs[a] = 1
mod = 10**9 + 7

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

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
import math
import sys

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

def nCr(n, r):
  c = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
  return c

a.insert(0, -1)
a.append(n+1)

cnt = 1

for i in range(m+1):

  if 0 < i < m and a[i] + 1 == a[i+1]:
    print('0')
    sys.exit()

  step = (a[i+1] - 1) - (a[i] + 1)
  pattern = 1
  for j in range(1, step//2 + 1):
    if j > (step - j) //2:
      j = step - 2*j
    pattern += nCr(step - j, j)
  cnt *= pattern

print(cnt%1000000007)

Submission status: Wrong Answer

Solution code:
def main():
    n,m =map(int, input().split())
    #idxへの行き方の通りをリスト化
    num_list = [0]*(n+2)
    num_list[0] = 1
    a_list =[int(input()) for _ in range(m)]
    a_list.append(0)
    count = 0
    div =1000000007
    for i in range(n):
        
        if num_list[i] ==0:
            continue
        if i+1 is not a_list[count]:
            num_list[i+1] += num_list[i]
        else:
            count +=1
            if i+2 is not a_list[count]:
                num_list[i+2] += num_list[i]
                continue
            else:
                return 0
        if i+2 is not a_list[count]:
            num_list[i+2] += num_list[i]
    #print(num_list)
    return num_list[-2]%div

if __name__=='__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():
    n,m =map(int, input().split())
    #idxへの行き方の通りをリスト化
    num_list = [0]*(n+2)
    num_list[0] = 1
    a_list =[int(input()) for _ in range(m)]
    a_list.append(0)
    count = 0
    div =1000000007
    for i in range(n):
        
        if num_list[i] ==0:
            continue
        if i+1 is not a_list[count]:
            num_list[i+1] += num_list[i]%div
        else:
            count +=1
            if i+2 is not a_list[count]:
                num_list[i+2] += num_list[i]%div
                continue
            else:
                return 0
        if i+2 is not a_list[count]:
            num_list[i+2] += num_list[i]%div
    #print(num_list)
    return num_list[-2]%div

if __name__=='__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import sys

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

def nCr(n, r):
  num = 1
  for i in range(r+1, n+1):
    num *= i
  return num


P = 1
for i in range(m):
  if a[i] + 1 == a[i+1]:
    print(0)
    sys.exit()

for i in range(1, m+2):
  step = a[i] - a[i-1] - 1
  pattern = 1
  for j in range(1, int(step/2+1)):
    pattern += nCr(step-j, j)
  P *= pattern 

print(P%1000000007)

Submission status: Wrong Answer

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

print(a)

mod = 10 ** 9 + 7

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

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
 
forbidden = []
for i in range(m):
  forbidden.append(int(input()))
forbidden = set(forbidden) 
ans = [1, 1]
if 1 in forbidden:
  ans[-1] = 0
for i in range(2,n+1):
  if i in forbidden:
    ans.append(0)
  else:
    ans.append(ans[-1]+ans[-2])
  if ans[-1] == 0 and ans[-2] == 0:
    print(0)
    break
  if i == n:
    print(ans[-1]%1000000007)
    break

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
 
forbidden = []
for i in range(m):
  forbidden.append(int(input()))
 
ans = [1, 1]
if 1 in forbidden:
  ans[-1] = 0
for i in range(2,n+1):
  if i in forbidden:
    ans.append(0)
  else:
    ans.append(ans[-1]+ans[-2])
  if ans[-1] == 0 and ans[-2] == 0:
    print(0)
    break
  if i == n:
    print(ans[-1]%1000000007)
    break

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
 
forbidden = []
for i in range(m):
  forbidden.append(int(input()))
 
ans = [1, 1]
if 1 in forbidden:
  ans[-1] = 0
for i in range(2,n+1):
  if i in forbidden:
    ans.append(0)
  else:
    ans.append(ans[-1]+ans[-2])
  if ans[-1] == 0 and ans[-2] == 0:
    print(0)
  if i == n:
    print(ans[-1]%1000000007)

Submission status: Wrong Answer

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

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

ways = 1
j = 0
while(j < n):
    if not j in a:
        tmp_ways = 0
        # 1step
        if not j + 1 in a:
            tmp_ways += 1
        # 2step
        if (not j + 2 in a) and (j < n - 1):
            tmp_ways += 1

        if tmp_ways == 2:
            ways *= 2
        elif tmp_ways == 0:
            ways = 0
            break
    #print(j, tmp_ways)
    j += 1

print(ways % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

MOD=10**9+7
N,M=map(int,input().split())
bad=set(map(int,sys.stdin))

a,b=0,1
for i in range(1,N+1):
    if i not in bad:
        a,b=b,(a+b)%MOD
    elif a>0:
        a,b=b,0
    else:
        break

print(b)

Submission status: Wrong Answer

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

dp=[0]*(N+1)
dp[0]=1
for _ in range(M):
    a=int(input())
    dp[a]=-1

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

if dp[-1]==-1:
    print(0)
else:
    print(dp[-1]%(10**9+7))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    if i == 1:
        dp[i] = dp[0]
    elif i in ais:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools
import math

def patterns(length_n):
    n1 = length_n
    n2 = 0
    e = 0
    while(n1>-1):
        e+= math.factorial(n1+n2)/(math.factorial(n1)*math.factorial(n2))
        n1 = n1-2
        n2 = n2 + 1
    
    return e

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

broken = []
broken.append(-1)

for i in range(M):
    broken.append(int(input()))
broken.append(N+1)

pattern = 1

for j in range(M+1):
    if (broken[j+1]-broken[j]-2==-1):
        print(0)
        exit()
    else:
        pattern =pattern * patterns(broken[j+1]-broken[j]-2)

print((pattern%1000000007))

Submission status: Wrong Answer

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

ans =[1] + [1] + [-1] * (n-1)

for i in range(2, n+1):
    if ans[i] != 0:
        ans[i] = (ans[i-1] + ans[i-2]) % mod
    if i in lis:
        ans[i] = 0

print(ans[n])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
mod = 10 ** 9 + 7

dp = [1] + [1] + [0] * (n - 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[-1] % mod)

Submission status: Wrong Answer

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

dp=[1]+['']*n

for i in a:
  dp[i]=0

if dp[1]=='':
  dp[1]=1
  

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

dp[0]=1

for i in range(1,n+1):
	if a[i] == 1:
		continue

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

	dp[i] = dp[i] % mod

print(dp[n]%mod)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
if 1 in a and 2 in a:
  print(0)
  exit()
elif 1 in a:
  ans=[0,1]
elif 2 in a:
  ans=[1,0]
else:
  ans=[1,2]

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

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc129/tasks/abc129_c
N,M = map(int,input().split())
dp = [[] for i in range(N)]
for i in range(M):
    dp[int(input())-1] = 0

for i in range(N):
    if dp[i] != 0:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1] + dp[i-2]
        
print(dp[-1])

Submission status: Wrong Answer

Solution code:
#https://atcoder.jp/contests/abc129/tasks/abc129_c
N,M = map(int,input().split())
dp = [[] for i in range(N)]
for i in range(M):
    dp[int(input())-1] = 0

for i in range(N):
    if dp[i] != 0:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 2
        else:
            dp[i] = dp[i-1] + dp[i-2]
        
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1

fib = [0] * MAX
fib[0], fib[1] = 1, 2
# for i, j in zip(a[:m-1], a[1:]):
#     if j - i == 1:
#         print(0)
#         exit()

for i in range(2, MAX):
    fib[i] = fib[i-1] + fib[i-2]

for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    if not between:
        continue
    ans *= fib[between-1]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
ans = 1
MOD = 10**9+7
MAX = 10**5+1

fib = [0] * MAX
fib[0], fib[1] = 1, 2
for i, j in zip(a[:m-1], a[1:]):
    if j - i == 1:
        print(0)
        exit()

for i in range(2, MAX):
    fib[i] = fib[i-1] + fib[i-2]
print(fib[:10])

for i in range(m+1):
    left = 0 if i == 0 else a[i-1] + 1
    right = n if i == m else a[i] - 1
    between = right - left
    if not between:
        continue
    ans *= fib[between-1]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

for n in range(1,N+1):
  if n in A:
    dp[n] = 0
  else:
    dp[n] = (dp[n-2]+dp[n-1])%(10**9+7)

print(dp[N])

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

    if len(a) > 1:
        for i in range(m-1):
            if a[i+1]-a[i] <= 1:
                return 0
    else:
        return Fib(n+2)%1000000007

    
    a = a + [n]
    l = [a[0]]
    for i in range(1, m):
        l.append(a[i]-a[i-1]-1)
    l = l + [a[-1]-a[-2]]
    ans = 1
    for i in l:
        ans *= Fib(i+1)

    return ans%1000000007


print(solve())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[15]:


from collections import deque


# In[33]:


N,M = map(int, input().split())
alist = [True]*N
for _ in range(M):
    alist[int(input())-1] = False


# In[35]:


dp = deque([0]*2)
dp[0] = 1
ans = 0
mod = 10**9+7
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        if alist[i-1] == False:
            dp.append(0)
        else:
            dp.append((dp[0] + dp[1])%mod)
        dp.popleft()
    ans = dp[-1]
print(ans)


# In[ ]:

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[15]:


from collections import deque


# In[33]:


N,M = map(int, input().split())
alist = [True]*N
for _ in range(M):
    alist[int(input())-1] = False


# In[35]:


dp = deque([0]*2)
dp[0] = 1
ans = 0
mod = 1000000007
if N == 1:
    ans = 1
else:
    if 1 in alist:
        dp[1] = 0
    else:
        dp[1] = 1
    for i in range(2,N+1):
        if alist[i-1] == False:
            dp.append(0)
        else:
            dp.append((dp[0] + dp[1])%mod)
        dp.popleft()
    ans = dp[-1]
print(ans)


# In[ ]:

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[9]:


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


# In[11]:


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


# In[ ]:

Submission status: Wrong Answer

Solution code:
INF = 1_000_000_007

N, M = list(map(int, input().split()))
A = [-1] + [int(input()) for _ in range(M)] + [N + 1]
res = 1
for i in range(M + 1):
    t = A[i + 1] - A[i] - 2
    if t < 0:
        res = 0
    else:
        if t <= 1:
            _t = 1
        elif t <= 3:
            _t = t
        else:
            _t = 2
            _b = (t - 1) // 2
            _a = t // 2 + 1
            _c = _a - _b
            b = 1
            for i in range(1, _b + 1):
                b *= i
            a = b
            for i in range(_b + 1, _a + 1):
                a *= i
            c = _a - _b
            for _ in range(_b):
                _t += a // b // c
                _a += 1
                a *= _a
                b //= _b
                _b -= 1
                _c += 1
                c *= _c
                _c += 1
                c *= _c
        res *= _t
print(res % INF)

Submission status: Wrong Answer

Solution code:

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

MAX = 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


if any(X[i + 1] - X[i] == 1 for i in range(M - 1)):
    print(0)
else:
    X = [0] + X + [N]
    ans = 1
    for i in range(M + 1):
        diff = X[i + 1] - X[i] - 1
        tmp = 0
        for n in range(diff // 2 + 1):
            tmp += comb(diff - n, n)
            tmp %= MOD
        ans = ans * tmp % MOD

    print(ans)

Submission status: Wrong Answer

Solution code:

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

MAX = 10 ** 5 + 1
MOD = 10 ** 9 + 7

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


if any(X[i + 1] - X[i] == 1 for i in range(M - 1)):
    print(0)
else:
    X = [0] + X + [N]
    ans = 1
    for i in range(M + 1):
        diff = X[i + 1] - X[i] - 1
        tmp = 0
        for n in range(diff // 2 + 1):
            tmp += comb(diff - n, n)
            tmp %= MOD
        ans = ans * tmp % MOD
        print(diff, tmp)

    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
seta = set([int(input()) for _ in range(m)])

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    elif N == 1:
        print(1)
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if A_list and N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i-1] > 1000000007:
            Dp_list[i-1] -= 1000000007
            Dp_list[i] -= 1000000007
    print(Dp_list[N]%1000000007)

Submission status: Wrong Answer

Solution code:
import math

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

n, m = (int(xi) for xi in input().split())

a = []
diff = 0
a0 = 0
a1 = 0
for xi in range(m):
    a0 = a1
    a1 = int(input())
    a.append(a1)
    if a1-a0>diff :
        diff=a1-a0

print(comb(n,diff))
print(diff)
print(a)

p = [1]
for xi in range(1,diff+1):
    add = 1
    for j in range(1, int(xi/2)):
        add += comb(xi-j,j)
    p.append(add)