Se acerca la navidad y hay muchos regalos en el árbol, todos diferentes, pero cada uno con un peso en kilogramos.

Ian se pregunta cuantas formas existen de ordenar los regalos con respecto a su peso. Ayudalo a aclarar esta duda.

Por ejemplo:

Si se tienen 3 regalos: {A,B,C} y sus pesos respectivamente {1,2,1}
Se tienen 2 formas de ordenarlos por su peso:

{A,C,B} o {C,A,B}.

Se le dará un entero 1<= n <= 10000, que es el número de regalos en el árbol de navidad.

A continuacion se lista los pesos, números enteros positivos 1<=P<=1000000000, de cada uno de los regalos en kilogramos.

Imprimir el número de formas diferentes en los que se puede ordenar los regalos. Como el número puede ser muy grande imprimir la respuesta módulo 1000000007.