Problem: 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.

Submission attempts (in order):
import operator
from functools import reduce


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(operator.mul, range(n, n-r, -1), 1)
    denom = reduce(operator.mul, range(1, r+1), 1)
    return numer // denom


def calc_step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = calc_step2patterns(num_step)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-1, step_dict) + step2patterns(num_step-2, step_dict)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)


import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-1, step_dict) + step2patterns(num_step-2, step_dict)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def calc_step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = calc_step2patterns(num_step)
        step_dict[num_step] = ret
        return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)


import sys
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-2, step_dict) + step2patterns(num_step-1, step_dict)
        step_dict[num_step] = ret
        return ret


sys.setrecursionlimit(100000)
num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)


import sys
import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step, step_dict):
    try:
        return step_dict[num_step]
    except KeyError:
        ret = step2patterns(num_step-1, step_dict) + step2patterns(num_step-2, step_dict)
        step_dict[num_step] = ret
        return ret


sys.setrecursionlimit(100000)
num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1, 2: 2}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1, d)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1, d)

print(num_pattern % 1000000007)
exit(0)


import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats



#     try:
#         return step_dict[num_step]
#     except KeyError:

#         step_dict[num_step] = ret
#         return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

    num_pattern %= 1000000007

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


import operator
from functools import reduce
from scipy.misc import comb


def ncr(n, r):
    return comb(n, r, exact=True)


def step2patterns(num_step):
    pats = 0
    for j in range(0, (num_step//2)+1):
        pats += ncr(num_step-j, j)
    return pats



#     try:
#         return step_dict[num_step]
#     except KeyError:

#         step_dict[num_step] = ret
#         return ret


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {}

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= step2patterns(dry_step - 1)

# last step
dry_step = num_stair - last_wet

num_pattern *= step2patterns(dry_step - 1)

print(num_pattern % 1000000007)
exit(0)


def exec_ncr(max_step, record_dict):
    for i in range(2, max_step+1):
        record_dict[i] = record_dict[i-1] + record_dict[i-2]


num_stair, num_wet = map(int, input().split(' '))

last_wet = -1
num_pattern = 1
d = {0: 1, 1: 1}
exec_ncr(num_stair, d)

for i in range(0, num_wet):
    wet = int(input())
    dry_step = wet - last_wet - 1
    last_wet = wet

    if dry_step <= 0:
        print('0')
        exit(0)

    elif dry_step == 1 or dry_step == 2:
        continue

    else:
        num_pattern *= d[dry_step-1]

# last step
dry_step = num_stair - last_wet

num_pattern *= d[dry_step-1]

print(num_pattern % 1000000007)
exit(0)


Verdicts: Runtime Error

Runtime Error

Runtime Error

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Time Limit Exceeded

Accepted