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:
import math
import numpy as np

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

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

diff = np.array(A)[1:] - np.array(A)[:-1]
if any(diff == 1) :
    print(0)
else :
    S = []
    A.insert(0, 0)
    A.insert(N-1, N)
    #print(A)
    D = list(np.array(A)[1:] - np.array(A)[:-1])
    for d in range(1, len(D) - 1) :
        D[d] -= 1
    R = []
    #print(D)
    for d in D :
        P = d - 1
        K = int(P / 2)
        T = 1
        for k in range(1, K+1) :
            T += combinations_count(P - k, k)
        R.append(T)
    ans = R[0]
    #print(R)
    for r in R[1:] :
        #print(ans)
        ans = ans * r % (10 ** 9 + 7)
    print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
 
n,m = map(int,input().split())
a = [-1]
for i in range(m):
  a.append(int(input()))
a.append(n+1)
  
@lru_cache(maxsize=1000)
def comb(n,k):
  m = 1
  if n<2*k:
    k = n-k
  for i in range(1,k+1):
    m = m*(n-i+1)/i
  return m
 
pat = 1
for i in range(m+1):
  step = a[i+1]-a[i]-2
  patj = 0
  if(step<0):
    pat = 0
    break
  for j in range(step//2+1):
    patj += comb(step-j,j)
  patj = int(patj%1000000007)
  pat = int(pat*patj%1000000007)
  
print(pat)

Submission status: Wrong Answer

Solution code:
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
  


  
  
N, M = map(int,input().split())
A = []
for i in range(M):
  a = int(input())
  A.append(a)
  
flag = False
A.append(N+1)
A.sort()
a_struct = []
cut = 0
#0~2, #4~6
for i in A:
  x = []
  for j in range(cut, i):
    x.append(j)
  a_struct.append(len(x)-1)
  cut = i+1

#print(x)
#print(a_struct)
sum_ = 1  

for i in a_struct:
  if i == -1:
    flag = True
  sho = int(i/2)
  amari = i%2
  ccc = 0
  for j in range(sho+1):
    count = 0
    if j == 0:
      ccc += 1
      #print('j')
      continue
    counter_1 =i-2*j 
    counter_2 = j
    count = cmb(counter_1+counter_2, counter_1)

    #print('count ', count)
    ccc += count
  sum_ *= ccc
    
print(a_struct)
if flag:
  print(0)
elif not flag:
  print(sum_%1000000007)

Submission status: Wrong Answer

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

mod=1000000007

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


if n==1:
  if m==0:
    print(1)
  else:
    print(0)
  exit()

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


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



a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

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

print(dp[n])

Submission status: Wrong Answer

Solution code:
print((2**92)%1000000007)

Submission status: Wrong Answer

Solution code:
from math import factorial
"m段登る時の登り方の総数"
def culc(m):
    s=0
    if m%2==1:
        m1=1 #1の個数
        m2=m//2 #2の個数
    else:
        m1=0
        m2=m//2
    while m2>=0:
        s+=int(factorial(m1+m2)/(factorial(m1)*factorial(m2)))
        m1+=2
        m2+=-1
    return s

N,M=map(int,input().split())
a=[-1]
b=[]
for i in range(M):
    a+=[int(input())]
    b+=[a[-1]-a[-2]-2]
    if a[-1]-a[-2]==1:
        b=[]
        break
else:
    b+=[N-a[-1]-1]


if b==[]:
    sm=0
else:
    b.sort()
    c=culc(b[0])
    sm=c
    s1=b[0]
    for i in b[1:]:
        if s1==i:
            sm=sm*c
        else:
            c=culc(i)
            sm=sm*c
print(sm%1000000007)

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
l=[]
m=[]
ans=1
for i in range(a):
    m.append(2)
for i in range(b):
   
    t=int(input()) 
    if(t>=2):
        m[t]=m[t]-1
        m[t-1]=m[t-1]-1
        m[t-2]=m[t-2]-1
    else:
        m[t]=m[t]-1
        m[t-1]=m[t-1]-1
m[a-1]=m[a-1]-1
#print(m)
for i in m:
    if(i==0):
        ans=0
        break
    ans*=i

print(ans%1000000007)

Submission status: Wrong Answer

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

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
def calc(ans):
    if M == 0:
        return cnt[N]

    for i in range(M): 
        if i == 0:
            if A[i] != 1:
                ans*= cnt[A[i]]
        elif i > 0 and i < M:
            ans*=cnt[A[i] - A[i-1]-1]

        if i == M-1:
            ans*= cnt[N - A[i]]
        
        if ans == 0:
            break
    
        ans %= amari
        
    return ans

print(calc(ans))

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
    elif(tmp != before):
        before = tmp
        a.append(tmp)


warukazu = 1000000007
if(frag):
    before = 0
    ans = 0
    if(m!=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:
        ans = fib(n - before)
        ans = ans % warukazu
        print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []

for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1

for a_ in a:
    hole = a_ - hole
    pattern *= fibo(hole-1)
    hole = a_
    
pattern *= fibo(N-hole-1)

print(pattern % 1000000007)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
for i in range(m):
    b=int(input())
    a.append(b)
c=[]
d=0
for i in a:
    c.append(i-d-1)
    d=i
c.append(n-d-1)

fib=[0,1,2]
for j in range(2, 100000):
    fib.append(fib[j]+fib[j-1])

if min(c)==0:
    if c.count(0)==1 and c[0]==0:
            ans=1
            for k in c[1:]:
                ans=(ans*fib[k])
            print(ans%1000000007)
    else:
        print(0)
else:
    ans=1
    for k in c:
        ans=(ans*fib[k])
    print(ans%1000000007)

Submission status: Wrong Answer

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

a = [0] * M
for i in range(M):
    a[i] = int(input())
    



memo = [-1] * (N+1)
memo[0] = 1

for i in range(M):
    memo[a[i]] = 0


for i in range(1,N+1):
    if i == 1 and memo[i]>=0:
        memo[i] = memo[i-1]
    elif memo[i] >= 0:
       memo[i] = 0
        ## memo[i] i 番目の階段にいくまでのルート数
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)

Submission status: Wrong Answer

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


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


ans = 1
for i in range(m + 1):
    if i == 0 or i == m:
        ra = a[i+1] - a[i] - 1
    else:
        ra = a[i+1] - a[i] - 2
    if ra < 0:
        if i == 0 or i == m:
            continue
        else:
            ans = 0
            break
    elif ra == 0:
        continue
    else:
        aaa = 1
        for n in range(1, ra // 2 + 1):
            length = ra - (2 * n) + n
            aaa += combinations_count(length, n)
        ans *= aaa

print(ans % 1000000007)

Submission status: Wrong Answer

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

def check(A):
    for m in range(M-1):
        if A[m+1]-A[m]==1:
            return False
    return True

def fibo(n):
    if n==0 or n==1:
        return 1
    else:
        L=[1,1]
        for i in range(2,n+1):
            L=[L[-1]]+[sum(L)]
        return L[-1]

def main(A,N):
    if check(A)==False:
        return 0
    else:
        A=[0]+A+[N+1]
        B=[A[n+1]-A[n]-2 for n in range(M+1)]
        x=1
        for b in B:
            x*=fibo(b)
        return x%mod

print(main(A,N))

Submission status: Wrong Answer

Solution code:
import math

def combnation(x,y):
    return math.factorial(x) // (math.factorial(x-y) * math.factorial(y))


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

DIV = 10**9+7

ans = 1
a_prev = aa[0]
for a in aa[1:]:
    steps = a - a_prev -1
    if steps == 0 and a_prev>0 and a < aa[-1]:
        ans = 0
        break
    tmp = 0
    for i in range(steps//2 + 1):
        
        tmp += combnation(steps-i, i)
        # print(ans, tmp,combnation(steps-i, i), i, steps, a_prev, a)
    a_prev=a
    ans = ans*tmp
    # print('-'*10)
# print(ans)
print(ans%DIV)

Submission status: Wrong Answer

Solution code:
from math import factorial


MOD = 1e9 + 7


def main():
    N, M = map(int, input().split())
    a_begin = -1
    ans = 1
    for _ in range(M):
        a_end = int(input())
        num_stair = a_end - a_begin - 1
        cand = 0
        if a_end == 1:
            cand = 1
        elif num_stair == 0:
            ans *= 0
        elif num_stair % 2 == 0:
            for y in range(num_stair // 2):
                x = num_stair - 1 - 2 * y
                cand += comb(x + y, y)
        else:
            for y in range((num_stair - 1) // 2 + 1):
                x = num_stair - 1 - 2 * y
                cand += comb(x + y, y)
        ans %= MOD
        ans *= cand % MOD
        a_begin = a_end
    a_end = N + 1
    num_stair = a_end - a_begin - 1
    cand = 0
    if num_stair == 0:
        ans *= 0
    elif num_stair % 2 == 0:
        for y in range(num_stair // 2):
            x = num_stair - 1 - 2 * y
            cand += comb(x + y, y)
    else:
        for y in range((num_stair - 1) // 2 + 1):
            x = num_stair - 1 - 2 * y
            cand += comb(x + y, y)
    ans %= MOD
    ans *= cand % MOD
    print(int(ans % MOD))
    return


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

sum_dev = 1000000007

current = n
route_num = 0

before = -1
route_nums = [0]

def make_route_num(length):
    if length == 0:
        return 1
    if length == 1:
        return 1
    if length == 2:
        return 2
    else:
        minus1 = 1
        minus2 = 2
        fibo=0
        for i in range(2, length):
            fibo = minus1 + minus2
            minus2 = minus1
            minus1 = fibo
        return fibo
print()
for i, a_i in enumerate(a):
    if a_i - before == 1:
        print(0)
        exit()
    routes = make_route_num(a_i - 1 - route_nums[-1])
    route_nums.append(routes)
    before = a_i

routes = make_route_num(n - 1 - route_nums[-1])
route_nums.append(routes)

route_sum = 1
for route in route_nums[1:]:
    route_sum *= route % sum_dev
print(route_sum)

Submission status: Wrong Answer

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

def convi(li):
    m=max(li)
    a=[1,2]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans


def count(li,n):
    t=0
    ans=1
    li2=[]
    for i in range(1,n+1):
        if i in li:
            if i+1 in li:
                return(0)
            else:
                li2.append(t)
                t=1
        else:
            t+=1
    if t>0:        
        li2.append(t)   

        
    print(li2)
        
    return convi(li2)

                

print(count(li,n)%1000000007)

Submission status: Wrong Answer

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

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
def calc(ans):
    if M == 0:
        return cnt[N]

    for i in range(M): 
        if i == 0:
            if A[i] != 1:
                ans*= cnt[A[i]]
        elif i > 0 and i < M:
            ans*=cnt[A[i] - A[i-1]-1]

        if i == M-1:
            if A[i] != N -1:
                ans*= cnt[N - A[i]]
        
        if ans == 0:
            break
    
        ans %= amari
        
    return ans

print(calc(ans))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
 
n,m = map(int,input().split())
a = [-1]
for i in range(m):
  a.append(int(input()))
a.append(n+1)
  
@lru_cache(maxsize=1000)
def comb(n,k):
  m = 1
  if n<2*k:
    k = n-k
  for i in range(1,k+1):
    m = m*(n-i+1)/i
  return m
 
pat = 1
for i in range(m+1):
  step = a[i+1]-a[i]-2
  patj = 0
  if(step<0):
    pat = 0
    break
  for j in range(step//2+1):
    patj += comb(step-j,j)
  pat = int(pat*patj%1000000007)
  
print(pat)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
F = [1,1]
for i in range(1,n):
    F.append((F[i]%(10**9+7)+F[i-1]%(10**9+7))%(10**9+7))


if n==1:
    print(1)
if n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(F[n])
    else:
        x=F[min(a)-1]
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*F[a[i]-a[i-1]-2])%(10**9+7)
        print(x)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
import math


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def stair_cmb(step, memo):
    try:
        return memo[step]
    except KeyError:
        sm = 0
        r = 0
        for n in range(step, math.ceil(step / 2) - 1, -1):
            sm = sm + cmb(n, r)
            r = r + 1
        return sm


cache = {}
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(int(input()))
current = 0
ans = 0
for a in A:
    if current == a:
        print(0)
        exit()
    stp = a - current - 1
    if stp == 0:
        current = current + 2
    elif stp == 1:
        current = current + 3
    else:
        if ans == 0:
            ans = stair_cmb(stp, cache)
        else:
            ans = ans * stair_cmb(stp, cache)
        current = a + 1

stp = N - current
if stp == 0:
    pass
elif stp == 1:
    pass
else:
    ans = ans * stair_cmb(stp, cache)
ans = ans % 1000000007

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul 
n,m = map(int, input().split())
al = list(map(int, [input() for i in range(m)]))
al.append(n + 1)
pl = []
pre = 0
for elm in al:
    if elm == 1:
        pre = elm + 1
        continue
    max = elm - 1 - pre
    res = 0
    f0 = 0
    f1 = 1
    for i in range(max):
        res = f0 + f1
        f0 = f1
        f1 = res
    pl.append(res)
    pre = elm + 1

print(reduce(mul, pl) % 1000000007)

Submission status: Wrong Answer

Solution code:
#from itertools import accumulate

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
    # 2段続いている場合は最上段にたどり着けない
    if len(a)>=2 and a[-2]+1 == a[-1]:
        print(0)
        exit()

l = [0] * (n+1)

for i in range(n+1):
    if i == 0:
        l[i] = 1
        continue
    
    if i == 1:
        l[i] = 1

    if i in a:
        l[i] = 0
    else:
        l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)

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
    
N,M = map(int,input().split())

broken = [1]+[0]*(M+1)
for i in range(M):
    broken[i+1] = int(input())
broken[-1] = N-1

step = [broken[i+1]-broken[i] for i in range(M+1)]

if 1 in step[1:-1]:
    print('0')
else:
    ans = 1
    for s in step:
        if s<2:
            continue
        a = Fib(s+2)
        ans = a*ans
    print(str(ans%1000000007))

Submission status: Wrong Answer

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

a = [0] * M
for i in range(M):
    a[i] = int(input())
    



memo = [-1] * (N+1)
memo[0] = 1

for i in range(M):
    memo[a[i]] = 0


for i in range(1,N+1):
    if i == 1:
        memo[i] = memo[i-1]
    if memo[i] >= 0:
       memo[i] = 0
        ## memo[i] i 番目の階段にいくまでのルート数
    else:
          memo[i] = memo[i-1] +memo[i-2]


print(memo[N] % 1000000007)

Submission status: Wrong Answer

Solution code:
from math import factorial
from functools import lru_cache

n,m = map(int,input().split())
a = [-1]
for i in range(m):
  a.append(int(input()))
a.append(n+1)
  
@lru_cache(maxsize=100000)
def comb(n,k):
  m = 1
  if n<2*k:
    k = n-k
  for i in range(1,k+1):
    m = m*(n-i+1)/i
  return m

pat = 1
for i in range(m+1):
  step = a[i+1]-a[i]-2
  patj = 0
  if(step<0):
    pat = 0
    break
  for j in range(step//2+1):
    patj += comb(j,step-j)
  patj = patj%1000000007
  pat = pat*patj%1000000007
  
print(int(pat))

Submission status: Wrong Answer

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


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


ans = 1
for i in range(m + 1):
    if i == 0 or i == m:
        ra = a[i+1] - a[i] - 1
    else:
        ra = a[i+1] - a[i] - 2
    if ra < 0:
        if i == 0 or i == m:
            continue
        else:
            ans = 0
            break
    else:
        aaa = 1
        for n in range(1, ra // 2 + 1):
            length = ra - (2 * n) + n
            aaa += combinations_count(length, n)
        ans *= aaa

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000) 

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    # mems = [False] * (N+1)

    cnts = [False] * (N+1)
    for i in range(N+1):
        c = 0
        if i in As:
            c = 0
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = cnts[i-2] + cnts[i-1]
        cnts[i] = c
        print("cnt[{}] = {}".format(str(i), str(c)))

    print(cnts[N]%1000000007)
    # for i in range(N-1):
    #     if i in As and i+1 in As:
    #         return 0 

    # def rec(target):
    #     if target in As:
    #         return 0
        
    #     if target == 1:
    #         return 1
        
    #     if target == 2:
    #         return 2 if 1 not in As else 1

    #     if not mems[target]:
    #         one = rec(target-1)
    #         two = rec(target-2)
    #         mems[target] = one + two
        
    #     return mems[target]
    # print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m=(int(i) for i in input().split())
a = [int(input()) for i in range(m)]
#print(n,m,a)

d=[0 for i in range(100000+10)]
p=1000000007
n=100
#a=[1, 23, 45, 67, 89]

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

print(d[100]%p)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
a.insert(0,0)
a.append(n)
b=[a[i+1]-a[i] for i in range(m+1)]
ans=1
z=[1,2]
for i in range(10**5):
    z.append(z[i]+z[i+1])
for i in b:
    if i!=0:
        ans =ans*z[i-1]
    if i==0:
        ans=0
print(ans%1000000007)

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
    
N,M = map(int,input().split())

broken = [1]+[0]*(M+1)
for i in range(M):
    broken[i+1] = int(input())
broken[-1] = N-1

step = [broken[i+1]-broken[i] for i in range(M+1)]

if 1 in step[1:-1]:
    print('0')
else:
    ans = 1
    for s in step:
        a = Fib(s+2)
#        print(a)
        ans *= a
    print(str(ans%1000000007))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)

n = 100
m = 5

a_arr = [1,23,45,67,89]
stock_arr = []

for idx in range(0, n):
  stock_arr.append(-1)


def calc_ans(idx):

  if idx == n:
    return 1
  elif idx > n:
    return 0
  
  if stock_arr[idx] >= 0:
    return stock_arr[idx]

  ans_plus_1 = 0
  ans_plus_2 = 0

  if (idx+1) in a_arr:
    # a_arr.remove((idx+1))
    pass
  else:
    ans_plus_1 = calc_ans(idx+1)

  if (idx+2) in a_arr:
    # a_arr.remove((idx+2))
    pass
  else:
    ans_plus_2 = calc_ans(idx+2)
  
  # print('idx=' + str(idx))
  # print('ans_plus_1=' + str(ans_plus_1))
  # print('ans_plus_2=' + str(ans_plus_2))

  ans = ans_plus_1 + ans_plus_2

  stock_arr[idx] = ans
  
  return ans

true_ans = calc_ans(0) % 1000000007

print(true_ans)

Submission status: Wrong Answer

Solution code:

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

counter_arr = [0]*(N+1)

counter_arr[0] = 1
next_broken = -1
if len(broken_lst) != 0:
    next_broken = broken_lst.pop(0)
last_broken = -1

for i in range(0, N-1):
    flug = 0
    if i+1 == next_broken:
        flug = 1
#        print("p0", i, counter_arr)
    elif i+1 == last_broken:
        pass
#        print("p1",i, counter_arr)
    else:
        counter_arr[i+1] += counter_arr[i]
        counter_arr[i+1] %= 10**9 + 7
#        print("p2",i,  counter_arr)

    if i + 2 == next_broken:
        flug = 1
#        print("p3",i, counter_arr)
    else:
        counter_arr[i+2] += counter_arr[i]
        counter_arr[i+2] %= 10**9 + 7
#        print("p4",i, counter_arr)
    
    if flug == 1:
        last_broken = next_broken
        if len(broken_lst) != 0:
            next_broken = broken_lst.pop(0)

if last_broken != N - 1:
    counter_arr[-1] += counter_arr[-2]
counter_arr[-1] %= 10**9 + 7

print(counter_arr[-1])

Submission status: Wrong Answer

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


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


ans = 1
for i in range(m + 1):
    if i == 0 or i == m:
        ra = a[i+1] - a[i] - 1
    else:
        ra = a[i+1] - a[i] - 2
    if ra < 1:
        if i == 0 or i == m:
            continue
        else:
            ans = 0
            break
    else:
        aaa = 1
        for n in range(1, ra // 2 + 1):
            length = ra - (2 * n) + n
            aaa += combinations_count(length, n)
        ans *= aaa

print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2, 3]
n_2, n_1 = 2, 3
for i in range(3, n):
    n_2, n_1 = n_1, (n_2+n_1)%(10**9+7)
    comb_list.append(n_1)
for _ in range(m):
    a = int(input())
    a_list.append(a)
start = 0
ans = 1
if m == 0:
    ans = comb_list[n]
else:
    for a in a_list+[n+1]:
        if a == 1:
            start = a + 1
            continue
        else:
            if start == a:
                ans = 0
                break
            else:
                tmp = a - start - 1
                ans = (ans * comb_list[tmp])%(10**9+7)
                if a == n-1:
                    break
                else:
                    start = a + 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
t = 0
sum = 1
for _ in range(m):
    a.append(int(input()))
for i in range(100000):
    fnext = t + 1
    snext = t + 2
    if(t == n):
        break
    else:
        if(fnext not in a and snext not in a):
            if(snext > n):
                t += 1
                sum *= 1
            else:
                t += 2
                sum *= 2
        elif(fnext not in a and snext in a):
            t += 1
            sum *= 1
        elif(fnext in a and snext not in a):
            t += 2
            sum *= 1
        elif(fnext in a and snext in a):
            sum = 0

print(sum % 1000000007)

Submission status: Wrong Answer

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

import sys

input = sys.stdin.readline

cnt = 0

def main():
    N, M = map(int, input().split())
    m = {}
    for l in sys.stdin:
        m[int(l.strip())] = True

    # N 個の階段における移動方法
    dp = [0 for _ in range(N+1)]
    dp[0] = 1
    dp[1] = 1 if 1 not in m else 0

    # N-1の移動パターン + N-2の移動パターン
    for i in range(1, N+1):
        if i in m:
            dp[i] = 0
            continue
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
    print(dp[N] % 1000000007)

main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
if N == 1:
    print(1)
    quit()
if M > N//2:
    print(0)
    quit()

A = list(int(input()) for _ in range(M))
idx = 0
P = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1
a = -1
if len(A):
    if 1 == A[idx]:
        dp[1] = 0
        idx += 1

if len(A) and len(A) != 1:
    for i in range(2, N+1):
        if i != A[idx]:
            dp[i] = (dp[i-1] + dp[i-2]) % P
        else:
            dp[i] = 0
            if idx < M-1:
                idx += 1
else:
    for i in range(2, N+1):
        dp[i] = (dp[i-1] + dp[i-2]) % P
print(dp[N])

Submission status: Wrong Answer

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

dp = [0,1,2,3,5,8]
def getdp(x):
  while len(dp) <= x:
    dp.append(dp[-2]+dp[-1])
  return dp[x]

def solve(broken):
  
  ans = 1
  for i in range(m):
    broken[i] = int(input())
    if i>0:
      if broken[i-1] + 1 is broken[i]:
        return 0
  broken = [-1] + broken + [n+1]
  for i in range(1,m+2):
    if broken[i]-broken[i-1]-2 <= 0:
      continue
    ans *= getdp(broken[i]-broken[i-1]-2) 
    ans %= 1000000007
  return ans

print(solve(broken))

Submission status: Wrong Answer

Solution code:
p = [0]*100001
p[0] = 1
p[1] = 1
p[2] = 2
ans = 1
flag = 0
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]

# print(l1)

if m == 0:
	print(p[n])
	flag = 1
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)
				flag = 1
				break
			else:
				if l1[i] == 0:
					ans = ans
				else:
					ans = ans * p[l1[i]-2]

if flag != 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] - before - 2
    if step == -1:
        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 = list(map(int, input().split()))
A =[0]*M
for i in range(M):
    A[i] = int(input())

amari = 1000000007
cnt = [0]*(N+1)
cnt[0] = 0
cnt[1] = 1
for i in range(2,N+1):
    t = (cnt[i-1]+cnt[i-2])
    cnt[i] = t % amari

ans = 1
for i in range(M): 
    if i == 0:
        if A[i] != 1:
            ans*= cnt[A[i]-1]
    elif i > 0 and i < M:
        ans*=cnt[A[i] - A[i-1]-1]

    if i == M-1:
        if A[i] != N -1:
            ans*= cnt[N - A[i]]
    
    if ans == 0:
        break
  
    ans %= amari

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
c = [0]*(N+1)
c[0] = 1
c[1] = 1
ans = 1
a = []
al = 0
for i in range(2,N+1):
    c[i] = c[i-1]+c[i-2]
for i in range(M):
    ai = int(input())
    if i == 0:
        a.append(ai)
    else:
        if ai - al == 1:
            print(0)
            exit()
        else:
            a.append(ai)
    al = ai

for i in range(M):
    if i == 0:
        ans *= c[a[i]-1]
        ans %= mod
    if i == M-1:
        ans *= c[N-a[i]-1]
        ans %= mod
    else:
        if a[i+1] != a[i]:
            ans *= c[a[i+1]-a[i]-2]
            ans %= mod
print(ans)