J. Скобочные последовательности без ограничений

Посчитайте количество правильных скобочных последовательностей длины $2n$ из круглых и квадратных скобок — теперь без всяких ограничений на вложенность.

В классе ограничение «внутри круглых нет квадратных» заставляло писать рекурренту. Без него ответ раскладывается на два независимых множителя: сначала выбирается форма скобочной последовательности, потом каждой паре независимо назначается тип.

Ограничение на $n$ выросло на два порядка — рекуррента за $O(n^2)$ уже не пройдёт.

Одна строка содержит число $n$ ($0 \le n \le 10^5$).

Одно число — количество последовательностей по модулю $10^9 + 7$.