Copiado al portapapeles
Descripción
Considere que se tiene un conjunto de tres elementos {a,b,c} todas la permutaciones de estos elementos son:
{a,b,c},{b,c,a},{a,c,b},{b,a,c}, {c,a,b},{c,b,a}
La forma de calcular la cantidad de permutaciones es calculando el factorial de la cantidad de elementos, en el ejemplo 3!=6.
Ahora elimine todos los elementos en los cual un elemento se encuentra en la misma posición en una de las permutaciones. Por ejemplo:
{a,b,c},{c,b,a}
el elemento {b} se encuentra en la misma posición por lo que quitamos estos. Quitando todos estos elementos queda:
{b,c,a},{c,a,b}
El resultado es 2, que se denomina sub factorial y se escribe como $ !3=2 $.
Para calcular los sub factoriales se puede utilizar una de las siguiente formulas:
$ !n=n!\sum_{k=0}^n \frac{(-1)^k}{k!} $
$!n = n[!(n-1)]+(-1)^k $
$!n = (n-1)[!(n-1)+!(n-2)] $
Entrada
La entrada consiste en múltiples casos de prueba. La primera linea indica cuantos casos de prueba hay. Luego siguen los casos de prueba uno por línea que consiste de un numero entero menor a 50
Salida
Por cada caso de prueba imprima el sub factorial de n modulo 100,000,001 en una línea.
Ejemplo Entrada
3 2 3 4
Ejemplo Salida
1 2 9