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:
def mul(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(0, 2*(c + 1), 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS
 
def mul_odd(c):
  ANS = 0
  for t, o in zip(range(c, -1, -1), range(1, 2*c + 3, 2)):
    ans = 1
    for m in range(t + o, max(t, o), -1):
      ans *= m 
    ANS += ans
  return ANS
 
N, M = map(int, input().split())
D = 0
A = [0]
ans = []
aans = 1
for i in range(M + 1):
  if i != M :
  	A.append(int(input()))
  else: 
    A.append(N + 1)
  diff = A[i + 1] - A[i]
  if (diff == 1) & (i != 0):
    print(0)
    D = 1
    break
  if i != 0:
  	temp = diff - 2
  else:
    temp = diff - 1
  if (temp) % 2 == 0:
    aans *= mul(temp//2)
  else:
    aans *= mul_odd(temp//2)
if D == 0:   
	print(aans % 1000000007)

Submission status: Wrong Answer

Solution code:
def fib(n):
    a1 = 2
    a2 = 1 
    if n==2:
        return 2
    elif n==1:
        return 1
    else:
        count = 1
        for i in range(n-2):
            count = a1 + a2
            a2 = a1
            a1 = count
        return count

N,M = list(map(int,input().split()))
ans = 1
z = False
if M == 0:
    print(fib(N)) 
else:
    a = [int(input()) for _ in range(M)]
    for i in range(M):
        if i != 0:
            if a[i]-a[i-1] != 1:
                ans *= fib(a[i]-a[i-1]-2)
            else:
                z = True
                break
        else:
            ans *= fib(a[i]-1)
    ans *= fib(N-a[-1]-1)
    if z:
        print(0)
    else:
        print(str(ans%1000000007))

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
holes = []
pos = [1] * (n+1)
ans = 1

def calc(n):
    if n == 0:
        return 1
    if n == 1:
        pos[1]  = 1
        return 1
    elif n == 2:
        pos[2] = 2
        return 2
    else:
        pos[n] = pos[n-1] + pos[n-2]
        return pos[n]

for i in range(n):
    calc(i)

for i in range(m):
    holes.append(int(input()))

for i in range(m):
    if i > 0 and holes[i] == holes[i - 1] + 1:
        print(0)
        sys.exit()

for i in range(len(holes)):
    # print("\n # i: " + str(i))
    # print("# holes[i]: " + str(holes[i]))
    if i == 0:
        if holes[i] == 1:
            ans = 1
        else:
            ans = calc(holes[i] - 1)
#        print("# ans: " + str(ans))
    else:
        ans = ans * (calc(holes[i] - holes[i - 1] - 2))
#        print("# ans: " + str(ans))

    if i == len(holes) - 1:
        # print("\nlast!")
        # print("holes[i]: " + str(holes[i]))
        # print("dif: " + str(n - holes[i]))

        if holes[i] == n:
            break

        ans = ans * (calc(n - holes[i] - 1))
#        print("# ans: " + str(ans))


print(ans % 1000000007)
#print(calc(0))

Submission status: Wrong Answer

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

MOD = 1000000007


def get_route_num(num):
    # print('step num', num)
    if num == 0:
        return 1
    if num < 4:
        return num
    prev_route = 3  # num = 3
    prev_prev_route = 2  # num = 2
    route = prev_route + prev_prev_route
    for _ in range(4, num + 1):
        route = prev_route + prev_prev_route
        prev_prev_route = prev_route
        prev_route = route
        # print('route', route)
    return route


if len(broken_stairs) == 0:
    print(get_route_num(N))
    exit()

cur = 0
possible_route = 1
for i in range(M):
    if not cur == 0 and broken_stairs[i] - cur == 0:
        print(0)
        exit()
    step = broken_stairs[i] - cur - 1
    possible_route *= (get_route_num(step) % MOD)
    # possible_route %= MOD
    cur = broken_stairs[i] + 1

possible_route *= (get_route_num(N - cur) % MOD)
print(possible_route)

Submission status: Wrong Answer

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

MOD = 1000000007


def get_route_num(num):
    # print('step num', num)
    if num == 0:
        return 1
    if num < 4:
        return num
    prev_route = 3  # num = 3
    prev_prev_route = 2  # num = 2
    route = prev_route + prev_prev_route
    for _ in range(4, num + 1):
        route = prev_route + prev_prev_route
        prev_prev_route = prev_route
        prev_route = route
        # print('route', route)
    return route


if len(broken_stairs) == 0:
    print(get_route_num(N))
    exit()

cur = 0
possible_route = 1
for i in range(M):
    if not cur == 0 and broken_stairs[i] - cur == 0:
        print(0)
        exit()
    step = broken_stairs[i] - cur - 1
    possible_route *= (get_route_num(step) % MOD)
    # possible_route %= MOD
    cur = broken_stairs[i] + 1

possible_route *= get_route_num(N - cur)
print(possible_route % MOD)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
bl = set([int(input())-1 for _ in range(m)])
l = [i for i in range(n)]

mod = 1000000007
al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()

    
li = [i for i in l if i>=2]

for i in li:
    if i not in bl:
        al[i] = (al[i-1] + al[i-2])%mod
        if al[i] == 0:
            print(0)
            exit()

print(al[-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib={0:0,1:1,2:1}
for i in range(3,100003):
    fib[i]=fib[i-1]+fib[i-2]
  #  fib.append(fib[i-1]+fib[i-2])

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
if m!=0:
    l=[a[0]]
    for i in range(len(a)-1):
        l.append(a[i+1]-a[i]-1)
    l.append(n-a[-1])
    k=1
    for i in l:
        k=fib[i]*k%mod
    print(k%mod)
else:
    print(fib[n+1])

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
lists = [1,2]
last = 0
conbi = 1

def conbination(num):
    if len(lists) >= num:
        return lists[num-1]
    for i in range(len(lists),num):
        lists.append(lists[i-1]+lists[i-2])
    return lists[num-1]

for i in range(m):
    step = int(input()) #穴が空いているステップ
    if step - last== 1:  #ラストステップが穴が空いているステップの次だったとき
        if last != 0:
            conbi = 0
            break
        else:
            last = step

            continue
    if step - last == 0:
        continue
    if last == 0:
        conbi = (conbi * conbination(step - last - 1)) % (1000000007)
    else:
        conbi = (conbi * conbination(step - last - 2))%(1000000007)
    last = step


if conbi != 0 or last + 1 != n:
    step = n
    conbi = (conbi * conbination(step - last - 1))%(1000000007)

print(conbi)

Submission status: Wrong Answer

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

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

def Fib(n, lst):    
    if n == 1:
      if (n in lst):
        return 0
      else:
        return 1
    elif n == 2:
      if (n in lst):
        return Fib(1, lst1)
      else:
        return Fib(1,lst1) + 1
    else:
      if (n in lst):
        return 0
      else:
        return Fib(n-1,lst1)+Fib(n-2,lst1)

lst2 = []
lst2 = [Fib(n, lst1) for n in range(1,N+1)]
print(lst2[-1] % 1000000007)

Submission status: Wrong Answer

Solution code:
n,_,*a=map(int,open(0).read().split())
a=set(a)
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(i not in a);c,d=n,c
print(n)

Submission status: Wrong Answer

Solution code:
import math
n, m = [int(i) for i in input().split()]
p = [0 for i in range(n + 1)]
for _ in range(m):
    p[int(input())] = 1
    
a = []
a.append(1)
if 1 in p:
    a.append(0)
else:
    a.append(1)
for i in range(2, n + 1):
    if p[i] == 1:
        a.append(0)
    else:
        a.append((a[i - 2] + a[i - 1]) % 1000000007)
    
print(a[n])

Submission status: Wrong Answer

Solution code:
def fib(n):
  a, b = 0, 1
  for i in range(n):
    a, b = b, a + b
  return b

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

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
holes = []
pos = [1] * (n+1)
ans = 1

def calc(n):
    if n == 0:
        return 1
    if n == 1:
        pos[1]  = 1
        return 1
    elif n == 2:
        pos[2] = 2
        return 2
    else:
        pos[n] = pos[n-1] + pos[n-2]
        return pos[n]

for i in range(n):
    calc(i)

for i in range(m):
    holes.append(int(input()))

for i in range(m):
    if i > 0 and holes[i] == holes[i - 1] + 1:
        print(0)
        sys.exit()

for i in range(len(holes)):
    if i == 0:
        if holes[i] == 1:
            ans = 1
        else:
            ans = calc(holes[i] - 1)

    else:
        ans = ans * (calc(holes[i] - holes[i - 1] - 2))


    if i == len(holes) - 1:


        ans = ans * (calc(n - holes[i] - 1))



print(ans % 1000000007)
#print(calc(0))

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if (i == 0):
        if (a[i] - 1 != 0):
            b.append(a[i] - 1)
    else:
        if (a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if (a[i] - a[i - 1] - 2 < 0):
            flag = True

    if (i == NM[1] - 1):
        if (NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if (flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
    answer = sum % (10 ** 9 + 7)
print(answer)

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i])
    answer = sum % (10**9 + 7)
print(answer)

Submission status: Wrong Answer

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

MOD = 1000000007


def get_route_num(num):
    # print('step num', num)
    if num == 0:
        return 1
    if num < 4:
        return num
    prev_route = 3  # num = 3
    prev_prev_route = 2  # num = 2
    route = prev_route + prev_prev_route
    for _ in range(4, num + 1):
        route = prev_route + prev_prev_route
        prev_prev_route = prev_route
        prev_route = route
        # print('route', route)
    return route


if len(broken_stairs) == 0:
    print(get_route_num(N))
    exit()

cur = 0
possible_route = 1
for i in range(M):
    if not cur == 0 and broken_stairs[i] - cur == 0:
        print(0)
        exit()
    step = broken_stairs[i] - cur - 1
    possible_route *= get_route_num(step)
    possible_route %= MOD
    cur = broken_stairs[i] + 1

possible_route *= get_route_num(N - cur)
print(possible_route % MOD)

Submission status: Wrong Answer

Solution code:
import sys
n, m = map(int, input().split())
holes = []
pos = [1] * (n+1)
ans = 1

def calc(n):
    if n == 1:
        pos[1]  = 1
        return 1
    elif n == 2:
        pos[2] = 2
        return 2
    else:
        pos[n] = pos[n-1] + pos[n-2]
        return pos[n]

for i in range(n):
    calc(i)

for i in range(m):
    holes.append(int(input()))

for i in range(m):
    if i > 0 and holes[i] == holes[i - 1] + 1:
        print(0)
        sys.exit()

for i in range(len(holes)):
    # print("\n # i: " + str(i))
    # print("# holes[i]: " + str(holes[i]))
    if i == 0:
        if holes[i] == 1:
            ans = 1
        else:
            ans = calc(holes[i] - 1)
#        print("# ans: " + str(ans))
    else:
        ans = ans * (calc(holes[i] - holes[i - 1] - 2))
#        print("# ans: " + str(ans))

    if i == len(holes) - 1:
        # print("\nlast!")
        # print("holes[i]: " + str(holes[i]))
        # print("dif: " + str(n - holes[i]))

        ans = ans * (calc(n - holes[i] - 1))
#        print("# ans: " + str(ans))

#print(ans)
print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0 and a[i] - 1 != 0):
        b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1 and NM[0] - a[i] - 1 != 0):
        b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i])
    answer = sum % (10**9 + 7)
print(answer)

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        b.append(a[i] - 1)
    else:
        b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i])
    answer = sum % (10**9 + 7)
print(answer)

Submission status: Wrong Answer

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


print("{}".format(dp[-1]))

Submission status: Wrong Answer

Solution code:
mod=10**9+7
N,M=map(int,input().split())
A=[int(input()) for m in range(M)]
L=[1 for n in range(N+1)]
for a in A:
    L[a]=0
Block=[0,1]
for n in range(1,N+1):
    if L[n]==1:
        Block=Block[1:]+[sum(Block)]
    else:
        Block=Block[1:]+[0]
print(Block[-1])

Submission status: Wrong Answer

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

a_list = []
former_a = -1
imp = False

for _ in range(M):
    a = int(input())
    a_list.append(a)
    if former_a < 0:
        former_a = a
    else:
        if a - former_a == 1:
            imp = True
            break

if imp:
    print(0)
else:
    
    def get_next(a1, length):
        if length < 3:
            return a1
        else:
            one, two = a1, a1
            for i in range(3, length+1, 1):
                ans = one + two
                two = one
                one = ans
            return ans
    if M == 0:
        print(get_next(1, N+1) % 1000000007)
    else:
    
        for idx, a in enumerate(a_list):
            if idx == 0:
                tyokuzen = get_next(1, a)

            else:
                tyokuzen = get_next(tyokuzen, a - a_list[idx-1] -1)

        ans =  get_next(tyokuzen, N - a_list[-1])

        print(ans % 1000000007)

Submission status: Wrong Answer

Solution code:
def culc(m):
    a1=0
    a2=1
    for i in range(m):
        a2_=a2
        a2=a1+a2
        a1=a2_
    return a2

N,M=map(int,input().split())
a1=-1
a2=0
b=[]
for i in range(M):

    a2=int(input())
    da=a2-a1
    a1=a2
    if da==1:
        b=[]
        break
    elif da!=0:
        b+=[da-2]

else:
    b+=[N-a2-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:
print(1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b if n >= 0 else 0

if M == 0:
    print(fib(N))
    exit()
'''
flag = 0
if M >= 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1
    if flag >= 1:
        print(0)
        exit()
'''
ans = fib(a[0]-1)
for i in range(M-1):
    ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
    answer = sum % (10**9 + 7)
print(0)

Submission status: Wrong Answer

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

def fib(n):
        a, b = 0, 1
        for i in range(n):
            a, b = b, a + b
        return b if n >= 0 else 0

if M == 0:
    print(fib(N))
    exit()
'''
flag = 0
if M >= 2:
    for i in range(M-1):
        if a[i+1] - a[i] == 1:
            flag += 1
    if flag >= 1:
        print(0)
        exit()
'''
ans = fib(a[0]-1)
for i in range(M-1):
    ans = (ans * fib(a[i+1]-a[i]-2))%(10**9+7)

ans = (ans * fib(N-a[-1]-1))%(10**9+7)

print(ans)

Submission status: Wrong Answer

Solution code:
# 2019 6/9
# ABC129 C Typical Stairs
# fn: ways from 0 to n
# f(n) = f(n-1) + f(n-2)
# DP

from sys import setrecursionlimit
setrecursionlimit(100000)


CNT = 0
dp_list = [-1] * (100000 + 5)


def check_hole(M, broken_stairs):
    if len(broken_stairs) <= 1:
        return True
    for i in range(M - 1):
        if broken_stairs[i + 1] - broken_stairs[i] == 1:
            return False
    return True


def fib(n):
    global dp_list
    if n == 0 or n == 1 or n == 2:
        dp_list[0] = 0
        dp_list[1] = 1
        dp_list[2] = 2
        return dp_list[n]
    if dp_list[n] != -1:
        return dp_list[n]
    else:
        dp_list[n] = fib(n-1) + fib(n-2)
        return dp_list[n]


def count(broken_stairs, top_N, M):
    head = 0
    count_list = []
    if M == 1:
        count_list.append(broken_stairs[0] - 1)
        count_list.append(top_N - broken_stairs[0])
        return count_list
    else:
        for i in range(M):
            count_list.append(broken_stairs[i] - head - 1)
            head = broken_stairs[i]
        count_list.append(top_N - broken_stairs[-1])
        return count_list


def find_ans(broken_stairs, top_N, M):
    global CNT
    tmp = 1
    holes = count(broken_stairs, top_N, M)
    for i in holes:
        tmp *= fib(i)
    return tmp


if __name__ == '__main__':
    # N, M = list(map(int, input().split()))
    # broken_stairs = []
    # for i in range(M):
    #     broken_stairs.append(int(input()))
    #
    # unable = check_hole(M, broken_stairs)
    # if not unable:
    #     print(0)
    # else:
    #     ans = find_ans(broken_stairs, N, M)
    #     print(ans % 1000000007)

    tmp = 1
    num = [0, 22, 22, 22, 22, 11]
    for i in num:
        tmp += fib(i)
        print(tmp % 1000000007)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = False
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = True

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
    answer = sum % (10**9 + 7)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg2 = 1
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
		if flg == 1:
			break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()

Submission status: Wrong Answer

Solution code:
def Fib(n):
    a,b = 1,1
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        for i in range(n-2):
            a,b = b,a+b
        return b
    
n,m = map(int,input().split())
start = []
for i in range(m):
    start.append(int(input()))

if start == []:
    print(Fib(n+1))
else:
    pstart = [-1]+start+[n+1] #スタートとゴールを追加
    newlist = [] #距離のリスト
    for j in range(len(pstart)-1):
        newlist.append(pstart[j+1]-pstart[j]) #障害物同士の距離を測る
    if 1 in newlist[1:len(newlist)-1]:
                 print(0)
    else: #ちゃんと距離が出そうなとき
        ans = 1
        #print(newlist)
        for w in newlist:
            #print(Fib(w-1))
            #print(ans)
            ans = (ans*Fib(w-1))%1000000007
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
inputs = sys.stdin.readline
def main():
	ans = 1
	a = 0
	b = 0
	flg2 = 0
	N, M = map(int,inputs().split())
	A =[0]*(M+1)
	for i in range(M):
		a = int(inputs())
		A[i] = a-1-b
		b = a + 1
	A[M] = N - b
	A.sort()
	if A [0] < 0:
		flg2 = 1
	p = 1
	q = 1
	t = 0
	flg = 0
	while (A[t]<2):
		t = t+1
		if t > M:
			flg2 = 1
			flg = 1
			break
	for k in range(2,N+1):
		r = p + q
		p = q
		q = r
		if flg == 1:
			break
		while (A[t] == k):
			ans = ans*r%1000000007
			t += 1
			if t == M+1:
				flg = 1
				break
	if flg2 == 0:
		print(ans%1000000007)
	else:
		print(0)
main()

Submission status: Wrong Answer

Solution code:
import math

"""def fib(n):
    f = (((1 + math.sqrt(5)) / 2)**n - ((1 - math.sqrt(5)) / 2)**n ) / math.sqrt(5)
    return int(f)"""
"""def fib(n):
    a, b = 0, 1
    if(n == 1):
        return a
    elif(n == 2):
        return b
    else:
        for _ in range(n-2):
            a, b = b, a + b
        return b"""


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d

    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)


def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a


NM = [int(i) for i in input().split()]
a = []
b = []
answer = 0
flag = True
for i in range(NM[1]):
    a.append(int(input()))
    if(i == 0):
        if(a[i] - 1 != 0):
            b.append(a[i] - 1)
        if(a[i] - 1 < 0):
            flag = False
    else:
        if(a[i] - a[i - 1] - 2 != 0):
            b.append(a[i] - a[i - 1] - 2)
        if(a[i] - a[i - 1] - 2 < 0):
            flag = False

    if(i == NM[1] - 1):
        if(NM[0] - a[i] - 1 != 0):
            b.append(NM[0] - a[i] - 1)
        if(NM[0] - a[i] - 1 < 0):
            flag = False

"""if(NM[1] > NM[0]/2):
    answer = 0"""
if(not flag):
    answer = 0
else:
    sum = 1
    for i in range(len(b)):
        sum *= fib(b[i] + 1)
    answer = sum % (10**9 + 7)
print(answer)