Вычисление каталонских чисел по модулю простого числа

Ниже приводится описание проблемы:

пусть c[n]будет каталонским номером для nи p— большое простое число, например. 1000000007

Мне нужно вычислить c[n] % p, где nварьируется от {1,2,3,...,1000}

Проблема, с которой я столкнулся, заключается в том, что на 32-битной машине вы получаете переполнение, когда вычисляете каталонское число для такого большого целого числа. Я знаком с модульной арифметикой. Также

(a.b) % p = ((a % p)(b % p)) % p 

эта формула помогает мне избежать переполнения в числителе отдельно, но я понятия не имею, как работать со знаменателями.