Many people could find the formula, due to the inclusion-exclusion principle, but also many people could not find a proper method to calculate the formula, especially under module p.

In fact, you don't need to calculate the huge combination numbers, nor do you need to perform some complex operations such as integer factorization. All you need is to rewrite the formula, and make it easier for calculation under module p.

The formulation from inclusion-exclusion principle is:
R = SUM (i = 0 to n) : (-1) ^ n * [(n + i)! / 2 ^ i] * C(n, i)
where C(N, i) is the combination number, which is also the most difficult part in the formula.

The key to calculation is rewrite the whole term, not only the combination number:
[(n + i)! / 2 ^ i] * C(n, i)
= [(n + i)! / 2 ^ i] * [n! / i! / (n - i)!]
= [(n + i)! * n!] / [2 ^ i * i! * (n - i)!]
= [(n + i)! / (n - i)!] / 2 ^ i * [n! / i!]

Now, please note that, [(n + i)! / (n - i)!] could be recursively calculated: we need only to multiple (n + i) and (n + 1 - i) to the previous calculation result. Fortunately, there must be an even number in every pair of (n + i) and (n + 1 - i). So the increasing power of 2 could be also recursively canceled.
Finally, the term [n! / i!] is easily calculated.

Therefore, we solved the problem without a DIVISION calculation, which is hard to perform under module p.

Hope this will help.

nice xD
one problem is that not everyone got exactly that formula, but instead another version of it. the fact that in your version of the formula you can obtain f(n) recursively only by multiplying two terms by f(n-1) makes it much easier. of course from the formula that i found i can get to yours, but thats more subtle.