Мне кажется, что моя формула верна.
Пусть f(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём любые два соседние числа различны; g(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём существует только одна пара соседних равных чисел.
Тогда f(n)=n*(2*n-2)*f(n-1)+n*g(n-1), g(n)=n*(2*n-1)*f(n-1)+n*g(n-1) => f(n)=g(n)-n*f(n-1) => g(n-1)=f(n-1)+(n-1)*f(n-2) => f(n)=n*((2*n-1)*f(n-1)+n*(n-1)*f(n-2)).
f(1)=0, f(2)=2 (mod p).
Ответ на задачу f(n-1) mod p.

Хотелось бы увидеть ответы на следующие тесты:
5 10000000
6 10000000
7 10000000

Edited by author 29.05.2017 13:01

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.

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?

1000 1000000007
100000 1000000007

thanks

In my opinion, for n=4 the correct answer is 20 if I understood the condition of the problem correctly, i.e for n=3 there are exists 2 ways:
123231 and 132321. Please, explain me my mistake if I'm wrong.