Level 1 Flat-to-flat sequences
You make exactly 2n trades, each either buy one share or sell one share. You start with no position, must finish with no position, and you can't short: your position may never drop below zero.
Write
def number_of_sequences(n: int) -> int
returning how many different buy/sell sequences satisfy this, modulo 1_000_000_007.
number_of_sequences(0) # 1 (the empty sequence)
number_of_sequences(1) # 1 (B S)
number_of_sequences(3) # 5 (BBBSSS, BBSBSS, BBSSBS, BSBBSS, BSBSBS)
Constraints: 0 <= n <= 2 * 10**5. Anything quadratic in n is far too slow; aim for about O(n) plus a modular inverse or two.
Show hint
The answers for n = 0, 1, 2, 3, 4, ... are 1, 1, 2, 5, 14, ..., a famous sequence with a closed form built from C(2n, n). Divisions mod the prime become multiplications by modular inverses.