answer = all - 1_pair_bad+ 2_pair_bad + ...+(-1)^i_pair_bad =
 (2*n-2)!/2^(n-1) -> //all permutations of set{2,2,3,3,n,n},
  //1 is the capital thats why don't included in set
 + sum(i=1,n-1)(-1)^i* //calculate bad permutations
  [C(i,n-1)*(2*n-2-i)!]/2^(n-1-i)
this formula has 2 disadvantages:
1)calculating each Bad(i) requires O(i) time - counting factorial and degree, so, counting all Bad permutations will be TL.
2) division prevents us simply take each summand by modulo - even if a/b -> integer ->   a/b  !=   (a%p)/(b%p)
---
We can avoid first disadvantage  - Bad(i) can be counted in O(1) using bad(i-1) but modulo taking problem are still here.
P/S
I now that integer fraction's modulo can be found with fast_exponention and euler_function (like #140 in acm.mipt.ru)
but i think it's not necessary here, i want solve  this problem in linear time without number theory/
May be some reccurence exists? Does anybody know?

Simple linear reccurence without number theory exists.

Formula easy may be found in literature.
Problem in computing binomials C[n,k] % p when n,k~10^5 and p is not prime.
I think that formula C[n,k]=C[n,k-1]*(n-k+1)/k may be used but in realization:
n-k+1=p1^(a1)*p2^(a2)...*pm^(am) and so for k also.
In other words we are working in prime basis.
In final answer all ai>=0 (because C[n,k] is int) and we don't need in finding
h^(-1) mod p for some h.

TLE...?
C(n,k) has a long sequnce of prime factors for all k(I thought that more short)
for example C(50,22)=(2^4)(7^2)(23^1)(29^1)(31^1)(37^1)(41^1)(43^1)(47^1). If find way
to work with part (23^1)(29^1)(31^1)(37^1)(41^1)(43^1)(47^1) more quickly would be all Ok.

Edited by author 04.04.2011 10:10

if p1, p2, ..., pk are the prime factors of p, you can precompute the factorials of all numbers in the following form

k = a * p1^e1 * ... pk^ek

for each factorial, keep the value a mod p and the exponents. now, with gcd(a,p) = 1 you can use modular inverses and subtract exponents in order to obtain the correct value of C(n,k) modulo p.