Problem statement

https://binarysearch.com/problems/Planar-Edges/

Solution

What in fact is asked is Catalan numbers here, so we can use direct formula after we precompute factorials and inverse factorials.

Complexity

It is O(n) for time and space.

Code

MOD, M = 10**9 + 7, 10**5//2
F = [1]*(M+1)
for i in range(1, M+1):
    F[i] = (F[i-1] * i) % MOD

I = [1]*M + [pow(F[M], MOD - 2, MOD)]
for i in range(M-1, 0, -1):
    I[i] = I[i+1]*(i+1) % MOD

class Solution:
    def solve(self, n):
        return (F[n] * I[n//2] * I[n//2 + 1]) % MOD