Какой самый быстрый (известный )алгоритм для нахождения n --го каталонского числа по модулю m?

Задача состоит в том, чтобы найти n -й каталонский номер по модулю m, где m— это НЕ простое , m = (10^14 + 7). Вот список методов, которые я пробовал:(максN = 10,000)

1. Динамическое программирование для просмотра таблицы -вверх, слишком медленно
2. Используйте каталонскую формулу ncr(2*n, n)/(n + 1), опять же, она была недостаточно быстрой из-за функции ncr, не может ускориться, используя возведение в степень , потому что mне простое число.
3. Жестко запрограммировать таблицу предварительно -, сгенерированную Catalans, но это не удалось из-за ограничения размера файла.
4. Рекуррентное соотношение C(i,k) = C(i-1,k-1) + C(i-1,k), это слишком медленно

Поэтому мне интересно, есть ли другой более быстрый алгоритм для нахождения n -th каталонского номера, о котором я не знаю?

Использование динамического программирования

void generate_catalan_numbers() {
    catalan[1] = 1;
    for (int i = 2; i <= MAX_NUMBERS; i++) {
        for (int j = 1; j <= i - 1; j++) {
            catalan[i] = (catalan[i] + ((catalan[j]) * catalan[i - j]) % MODULO) % MODULO;
        }
        catalan[i] = catalan[i] % MODULO;
    }
}

Используя исходную формулу

ull n_choose_r(ull n, ull r) {
    if (n < r)
        return 0;

    if (r > n/2) {
        r = n - r;
    }

    ull result = 1;
    ull common_divisor;
    for (int i = 1; i <= r; ++i) {
        common_divisor = gcd(result, i);
        result /= common_divisor;
        result *= (n - i + 1) / (i / common_divisor);
    }

    return result;
}

Использование рекуррентного соотношения

ull n_choose_r_relation(ull n, ull r) {
    for (int i = 0; i <= n + 1; ++i) {
        for (int k = 0; k <= r && k <= i; ++k) {
            if (k == 0 || k == i) {
                ncr[i][k] = 1;
            }
            else {
                ncr[i][k] = (ncr[i - 1][k - 1] + ncr[i - 1][k]) % MODULO;
            }
        }
    }

    return ncr[n][r];
}