Модуль на комбинаториалах

Question

Предположим, что число n, и мы должны найти сумму всех комбинаториалов n, т.е. nC0+nC1+nC2+...+ nCn. Результат может быть большим, поэтому окончательный ответ должен быть суммой%D (D=10^9+7).

Подход, который я использовал,

long sum=0;
long combination=1;
for(int i=1;i<=n;i++){
   combination=((combination*(n-i+1))/i)%D;
   sum=(sum+combination)%D;
}

Но это не работает.

Реальное постановление задачи и код. Код дает правильный вывод до n=20.

Answer 1

Вы должны изменить конечный результат, а не на каждом этапе.
Также числа становятся очень большими, поэтому используйте BigInteger вместо long.

Вот мое решение
http://ide.geeksforgeeks.org/Ew3Epn

Используя формулу (2*n)!/(N!)^2
нашел здесь -> https://oeis.org/A000984