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: Runtime Error

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

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

print(dp[n])

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
dic =[0]*12345
for _ in range(m):
	dic[int(input())]+=1

mod=10**9+7
if n==1:
	print(1)
	exit()
dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if dic[1]!=1 else 0

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

dp = [0]*(n+1)
dp[0]=1
dp[1]=1 if a[0]!=1 else 0

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

Submission status: Runtime Error

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

def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    elif x == 2:
        return(2)
    else:
        return(f(x-1) + f(x-2))

ans = 0
MOD = 10**9 + 7

if M == 0:
    ans += f(N) % MOD
    print(ans)
else:
    ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    for i in range(1, M): # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break
    ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    print(ans % MOD)

Submission status: Runtime Error

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

MOD = 10**9 + 7

def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    elif x == 2:
        return(2)
    else:
        return(f(x-1) % MOD + f(x-2) % MOD)

ans = 0

for i in range(M+1): # iは0からM
    if i == 0:
        ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    elif i == M:
        ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    else: # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break

print(ans % MOD)

Submission status: Runtime Error

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

def f(x): # フィボナッチ数列
    if x == 0:
        return(1)
    elif x == 1:
        return(1)
    elif x == 2:
        return(2)
    else:
        return(f(x-1) + f(x-2))

ans = 0
MOD = 10**9 + 7

for i in range(M+1): # iは0からM
    if i == 0:
        ans += f((a[0]-1) - 0) % MOD # 0段目からa_0-1段目に上る(その後a_0段目を飛ばしてa_0+1段目に上る)
    elif i == M:
        ans *= f(N - (a[M-1] + 1)) % MOD # a_M-1段目からN段目に上る
    else: # iは1からM-1
        stair = (a[i] - 1) - (a[i-1] + 1) # 登る段数
        if stair >= 0:
            ans *= f(stair) % MOD # a_(i-1)+1段目からa_i-1段目に上る(その後a_i段目を飛ばしてa_i+1段目に上る)
        else:
            ans = 0
            break

print(ans % MOD)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
fib=[0]*(n+1)
fib[0]=0
fib[1]=1
for i in range(n-1):
  fib[i+2]=fib[i]+fib[i+1]
ans=1
k=0
for i in range(m):
  a=int(input())
  ans*=fib[a-k]
  k=a+1
ans*=fib[n-k+1]
print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import sys

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

if N == 1:
    print(1)

else:
    a = 1
    ans = 1

    if M == 0:
        ans = (a+b)%1000000007
        a, b = b, ans

    elif M == 1:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if a_list[0] == i:
                a, b = b, 0
            else:
                ans = (a+b)%1000000007
                a, b = b, ans

    else:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if m < M-1:
                if a_list[m+1] - a_list[m] == 1:
                    print(0)
                    sys.exit()

                if a_list[m] == i:
                    a, b = b, 0
                    m += 1
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

            else:
                if a_list[m] == i:
                    a, b = b, 0
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

    print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

if N == 1:
    print(1)

else:
    a = 1
    ans = 1

    if M == 0:
        ans = (a+b)%1000000007
        a, b = b, ans

    elif M == 1:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if a_list[0] == i:
                a, b = b, 0
            else:
                ans = (a+b)%1000000007
                a, b = b, ans

    else:
        if a_list[0] == 1:
            b = 0
            m = 1
        else:
            b = 1
            m = 0
        for i in range(2, N+1):
            if m < M-1:
                if a_list[m+1] - a_list[m] == 1:
                    print(0)
                    sys.exit()

                if a_list[m] == i:
                    a, b = b, 0
                    m += 1
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

            else:
                if a_list[m] == i:
                    a, b = b, 0
                else:
                    ans = (a+b)%1000000007
                    a, b = b, ans

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
if n==1:
  print(1)

if n>1:
  a=[1]*n
  for i in range(m):
    a[int(input())-1]=0
  a[1]=a[0]+1
  for i in range(2,n):
    if a[i]==0:continue
    else:a[i]=a[i-1]+a[i-2]
print(a[n-1]%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
stairs = [0, 1]
for i in range(2, n+1):
    stairs.append((stairs[i-1] + stairs[i-2]) % mod)

count = 1
for i in range(m+1):
    diff = a[i+1] - a[i] - 1
    count *= stairs[diff]
print(count % mod)

Submission status: Runtime Error

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

stairs = [0, 1]
for i in range(2, n+1):
    stairs.append(stairs[i-1] + stairs[i-2])

mod = 10 ** 9 + 7
count = 1
for i in range(m+1):
    diff = a[i+1] - a[i] - 1
    count *= stairs[diff]
print(count % mod)

Submission status: Runtime Error

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

stairs = [0, 1, 1]
for i in range(3, n+1):
    stairs.append(stairs[i-1] + stairs[i-2])

mod = 10 ** 9 + 7
count = 1
for i in range(m+1):
    diff = a[i+1] - a[i] - 1
    count *= stairs[diff]
print(count % mod)

Submission status: Runtime Error

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

stairs = [0, 1, 1]
for i in range(3, n+1):
    stairs.append(stairs[i-1] + stairs[i-2])

def ans():
    mod = 10 ** 9 + 7
    count = 1
    for i in range(m+1):
        diff = a[i+1] - a[i] - 1
        if diff == 0:
            print("0")
            return
        else:
            count *= stairs[diff]
    print(count % mod)
    return

ans()

Submission status: Runtime Error

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

def f(stairs):
    if stairs == 1 or stairs == 2:
        return 1
    else:
        return f(stairs-1) + f(stairs-2)

def ans():
    mod = 10 ** 9 + 7
    count = 1
    for i in range(m+1):
        diff = a[i+1] - a[i] - 1
        if diff == 0:
            print("0")
            return
        else:
            count *= f(diff)
    print(count % mod)
    return

ans()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
A = []

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    # print(d)
    if x in A:
        d[x] = 0
        return 0
    if x > N:
        d[x] = 0
        return 0
    if x == N:
        d[x] = 1
        return 1

    if d.get(x):
        return d[x]

    if d.get(x + 1):
        x1 = d.get(x + 1)
    else:
        x1 = f(x + 1)
        d[x + 1] = x1

    if d.get(x + 2):
        x2 = d.get(x + 2)
    else:
        x2 = f(x + 2)
        d[x + 2] = x2

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
A = []

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    # print(d)
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    if d.get(x + 1):
        x1 = d.get(x + 1)
    else:
        x1 = f(x + 1)
        d[x + 1] = x1

    if d.get(x + 2):
        x2 = d.get(x + 2)
    else:
        x2 = f(x + 2)
        d[x + 2] = x2

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
A = []

for _ in range(M):
    a = int(input())
    A.append(a)

# d = {}


def f(x):
    print(d)
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    if d.get(x + 1):
        x1 = d.get(x + 1)
    else:
        x1 = f(x + 1)
        d[x + 1] = x1

    if d.get(x + 2):
        x2 = d.get(x + 2)
    else:
        x2 = f(x + 2)
        d[x + 2] = x2

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

N, M = map(int, input().split())
A = []

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    # print(d)
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2
    #
    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

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

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    # print(d)
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2
    #
    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

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

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    if d.get(x + 1):
        x1 = d.get(x + 1)
    else:
        x1 = f(x + 1)
        d[x + 1] = x1

    if d.get(x + 2):
        x2 = d.get(x + 2)
    else:
        x2 = f(x + 2)
        d[x + 2] = x2

    ans = x1 + x2
    d[x] = ans
    return ans


print(f(0) % 1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):
    a, b = 1, 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())
a = [int(input()) for _ in range(M)]
m = Fib(a[0])*Fib(N-a[M-1])
flag = True
for i in range(M-1):
    if a[i] + 1 == a[i+1]:
        print(0)
        flag = False
        break
if flag:
    for j in range(M-1):
        dev = a[j+1]-a[j]
        m = m*Fib(dev)
    print(m%1000000007)

Submission status: Runtime Error

Solution code:
def Fib(n):
    a, b = 1, 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())
a = [int(input()) for _ in range(M)]
m = Fib(a[0])*Fib(N-a[M-1])
flag = True
for i in range(M-1):
  if a[i] + 1 == a[i+1]:
    print(0)
    flag = False
    break
if flag:
    for j in range(M-1):
        dev = a[j+1]-a[j]
        m = m*Fib(dev)
    print(m%1000000007)

Submission status: Runtime Error

Solution code:
z=list(map(int,input().split()))
n,m,b=z[0],z[1],[1]
a=[int(input()) for i in range(m)]
if a[0]==1:
    b.append(0)
    c=1
else:
    b.append(1)
    c=0
for i in range(n-1):
    if c<len(a):
        if i+2==a[c]:
            b.append(0)
            c+=1
        else:
            b.append(b[i]+b[i+1])
    else:
        b.append(b[i]+b[i+1])
print(b[-1]%1000000007)

Submission status: Runtime Error

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

n,m=map(int(i) ,input().split())
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in a1:
    a3=i-1-a2
    c2=0
    for j in range(a3//2+1):
        c2+=combinations_count(a3-j,j)
    c1=(c1*c2)%(1000000007)
    a2=i+1
    if c1==0:
        break



print(c1)

Submission status: Runtime Error

Solution code:
#フィボナッチ数列か…
#c問題も解けないのか…
#典型問題なんだろうな
#踏めない段の分は除いて考えれば良い
n,m=input().split()
n,m=int(n),int(m)
ax=[int(input()) for i in range(m)]
bx=[1,1]
if ax[0]==1:
    bx[1]=0
for i in range(2,n+1):
    if i in ax:
        bx.append(0)
    else:
        bx.append((bx[i-2]+bx[i-1])%1000000007)
print(bx)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def nCk(n, k):
    return bunshi(n,k)/bunbo(k)
def bunshi(n,k):
    p = 1
    for i in range(k):
        p = p*(n-i)
    return p
def bunbo(k):
    p = 1
    for i in range(k):
        p = p*(i+1)
    return p
    

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    temp = 0
    for j in range(D[i]//2+1):
        temp += (nCk(D[i]-j,j)%1000000007)
    ans=(ans%1000000007)*(temp%1000000007)
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
def nCk(n, k):
    return bunbo(n,k)/bunshi(k)
def bunbo(n,k):
    p = 1
    for i in range(k):
        p = p*(n-i)
    return p
def bunshi(k):
    p = 1
    for i in range(k):
        p = p*(i+1)
    return p
    

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)

ans=1
for i in range(len(D)):
    temp = 0
    for j in range(D[i]//2+1):
        temp += nCk(D[i]-j,j)
    ans=(ans%1000000007)*(temp%1000000007)
print(int(ans%1000000007))

Submission status: Runtime Error

Solution code:
import fractions

N, M = map(int,input().split())
a=[-1]
for i in range(M):
    a.append(int(input()))
a.append(N+1)
#print(a)
D=[]
for i in range(M+1):
    D.append((a[i+1]-1)-(a[i]+1))
#print(D)
def nCk(n, k):
    return fractions.factorial(n)/(fractions.factorial(k)*fractions.factorial(n-k))
ans=1
for i in range(len(D)):
    if i !=len(D) and i!=0 and D[i]==0:
        temp = 0
    else:
        temp = 0
        for j in range(D[i]//2+1):
            temp += nCk(D[i]-j,j)
#    print(temp)
    ans=(ans*temp)%1000000007
print(int(ans%1000000007))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#一時間以上かかった
#一つだけTLE
#そっから30ぷん

from scipy.special import comb
n,m=[int(i) for i in input().split()]
a1=[int(input()) for i in range(m)]
a1.append(n+1)
c1=1
a2=0
for i in range(m+1):
    a3=a1[i]-1-a2
    c2=0
    for j in range(0,a3//2+1):
        c2+=comb(a3-j,j,exact=True)
    c1=(c1*c2)%(1000000007)
    a2=a1[i]+1
    if c1==0:
        break



print(c1)

Submission status: Runtime Error

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

a=[]
n,m = map(int, input().split())
if m != 0:
        for _ in range(m):
                a.append(int(input()))
else:
        print(n//2+1)

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

ans = (a[0]-1)//2 + 1

for i in range(1,m):
        tmp = a[i]-a[i-1] - 1
        
        ans *= tmp//2 + 1
        # print("i: "+str(i))
        # print("tmp: "+str(tmp))
        # print("ans: "+str(ans))
        # print("------------")
ans *= (n - a[-1])//2 + 1
print(ans%(10**9+7))

Submission status: Runtime Error

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

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

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

ans = (a[0]-1)//2 + 1

for i in range(1,m):
        tmp = a[i]-a[i-1] - 1
        
        ans *= tmp//2 + 1
        # print("i: "+str(i))
        # print("tmp: "+str(tmp))
        # print("ans: "+str(ans))
        # print("------------")
ans *= (n - a[-1])//2 + 1
print(ans%(10**9+7))

Submission status: Runtime Error

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

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

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

ans = (a[0]-1)//2 + 1

for i in range(1,m):
        tmp = a[i]-a[i-1] - 1
        
        ans *= tmp//2 + 1
        # print("i: "+str(i))
        # print("tmp: "+str(tmp))
        # print("ans: "+str(ans))
        # print("------------")
ans *= (n - a[-1])//2 + 1
print(ans%(10**9+7))

Submission status: Runtime Error

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

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

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

ans = (a[0]-1)//2 + 1

for i in range(1,m):
        tmp = a[i]-a[i-1] - 1
        
        ans *= tmp//2 + 1
        print("i: "+str(i))
        print("tmp: "+str(tmp))
        print("ans: "+str(ans))
        print("------------")
ans *= (n - a[-1])//2 + 1
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:

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

def fib(x):
    a = 1
    b = 1
    if x == 0:
        return 0
    elif x == 1:
        return a
    elif x == 2:
        return b
    else:
        for i in range(x-2):
            c = a + b
            a = b
            b = c
        return b 

before_a=1
output = fib(A[0])
if M>=1:
    for i in range(M-1):
        output *= fib(A[i+1]-A[i]-1)
    output *= fib(N-A[M-1])
else:
    output *= fib(N+1)
print(output%1000000007)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
n = [0] * N
n[0] = 1
n[1] = 2

#listの中をinで探すのはくっそ遅い
if N == 1:
    print(1)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1
if 2 in a:
    n[1] = 0

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

print(n[N - 1])

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
n = [0] * N
n[0] = 1
n[1] = 2

#listの中をinで探すのはくっそ遅い
if N == 1:
    print(1)
    exit()
if 1 in a and 2 in a:
    print(0)
    exit()
if 1 in a:
    n[0] = 0
    n[1] = 1
if 2 in a:
    n[1] = 0

for i in range(2, N):
    if i + 1 in a:
        pass
    else:
        n[i] = (n[i - 1] + n[i - 2]) % 1000000007

print(n[N - 1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

def fib(n):
    x =np.sqrt(5) 
    return int(1/x * ( ((1+x)/2)**n - ((1-x)/2)**n ) )

before_a=0
output = 1
A.append(N)
for a in A:
    sa = a-before_a
    before_a = a
    output *= fib(sa)

for i in range(len(A)-1):
    if A[i]+1 == A[i+1]:
        output=0
        break
print(output%1000000007)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split(' '))
if m > 0:
    aaa = set(map(int, sys.stdin))
else:
    aaa = set()

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-1]+dp[i-2])%mod

print(dp[n])

Submission status: Runtime Error

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

flag = 0
for i in range(m-1):
    if a[i+1] - a[i] == 0:
        flag = 1
        print(0)
        break

if flag == 0:
    b = [1]
    if a[0] == 1:
        b.append(0)
        a.pop(0)
    else:
        b.append(1)
    for i in range(2, n+1):
        if len(a) != 0 and a[0] == i:
            b.append(0)
            a.pop(0)
        else:
            b.append((b[i-1]+b[i-2])%1000000007)

    print(b[-1])

Submission status: Runtime Error

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

flag = 0
for i in range(m-1):
    if a[i+1] - a[i] == 0:
        flag = 1
        print(0)
        break

if flag == 0:
    b = [1]
    if a[0] == 1:
        b.append(0)
        a.pop(0)
    else:
        b.append(1)
    for i in range(2, n+1):
        if len(a) != 0 and a[0] == i:
            b.append(0)
            a.pop(0)
        else:
            b.append((b[i-1]+b[i-2])%1000000007)

print(b[-1])

Submission status: Runtime Error

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

NUM = int(10**9 + 7)

split = [[0, nums[0] - 1]]
for i in range(1, m):
    split.append([nums[i - 1] + 1, nums[i] - 1])
split.append([nums[-1] + 1, n])

n_steps = [h - l for l, h in split]

counts = [1, 1, 2]
for _ in range(max(n_steps) - 2):
    c = counts[-1] + counts[-2]
    counts.append(c)

if min(n_steps) < 0:
    print(0)
else:
    res = 1
    for s in n_steps:
        res *= counts[s]
        res %= NUM
    print(res)

Submission status: Runtime Error

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

dp = [1, 2]
if M != 0:
    A = [int(input()) for _ in range(M)]
    if A[0] == 1:
        dp = [0, 1]
    elif A[0] == 2:
        dp = [1, 0]

MOD = 1000000007

if N == 1:
    print (1)
if N == 2:
    print (dp[-1])
else:
    cnt = 0
    for n in range(2, N):
        while(cnt != M - 1 and A[cnt] < n + 1):
            cnt += 1
        if A[cnt] == n + 1:
            dp[0] = dp[1]
            dp[1] = 0
        else:
            new_val = (max(dp[0], 0) + max(dp[1], 0)) % MOD
            dp[0] = dp[1]
            dp[1] = new_val

print (dp[-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1

if dp[0] == -1 and dp[1] == -1:
    pass
else:
    if dp[0] == -1:
        dp[1] = 1
    elif dp[1] == -1:
        dp[0] = 1
    else:
        dp[0] = 1
        dp[1] = 2


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1

if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())

MOD = 1000000007
dp = np.zeros(N, dtype = int)
if M != 0:
    A = np.array([int(input()) for _ in range(M)], dtype = int)
    dp[A - 1] = -1

if dp[0] == -1 and dp[1] == -1:
    pass
elif dp[0] == -1:
    dp[1] = 1
elif dp[1] == -1:
    dp[0] = 1
else:
    dp[0] = 1
    dp[1] = 2


if N >= 3:
    for n in range(2, N):
        if dp[n] != -1:
            dp[n] = (max(dp[n-1], 0) + max(dp[n-2], 0)) % MOD

print (dp[-1])