Задача на комбинаторику(ПСП)

Ограничение по времени работы: 1 секунда

Посчитайте количество правильных скобочных последовательностей длины 2n (n открывающих скобок и n закрывающих), составленных из круглых и квадратных скобок так, что внутри любой пары круглых скобок нет квадратных скобок.

Например при n = 5, ответ 625.

Входные данные В единственной строке через пробел записано целое неотрицательное число n, не превосходящее 1000.

Выходные данные Выведите остаток от деления количества искомых правильных скобочных последовательностей на 10^9 + 7. Ниже приведён мой код.

#include <iostream>
#include <cmath>
using namespace std;
long long MOD = 1e9 + 7;
long long binomialCoefficient(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k > n - k) {
        k = n - k;
    }
    long long res = 1;
    for (int i = 0; i < k; ++i) {
        res = (res * (n - i)) / (i + 1);
    }
    return res;
}
long long a(int n) {
    long long sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += (((binomialCoefficient(2 * i + 1, i) * binomialCoefficient(2 * n - 1, n - i - 1)) / (2 * n - 1)) % MOD);
        sum %= MOD;
    }
    return sum;
}
int main() {
    int n;
    cin >> n;
    long long result = a(n + 1);
    cout << result % MOD;
}

Мне кажется он правильный, но у моего кода бывает переполнение, видимо я где-то не беру по модулю(1e9 + 7). Скажите пожалуйста, что исправить!