Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0198 - ALGEBRAIC TEAMWORK

   The great pioneers of group theory and linear algebra want to cooperate and join their theories. In group theory, permutations – also known as bijective functions – play an important role. For a finite set A, a function σ : A A is called a permutation of A if and only if there is some function

ρ : A A with σ(ρ(a)) = a and ρ(σ(a)) = a for all a A.

   The other half of the new team – the experts on linear algebra – deal a lot with idempotent functions. They appear as projections when computing shadows in 3D games or as closure operators like the transitive closure, just to name a few examples. A function p : A A is called idempotent if and only if

p(p(a)) = p(a) for all a A.

   To continue with their joined research, they need your help. The team is interested in non-idempotent permutations of a given finite set A. As a first step, they discovered that the result only depends on the set’s size. For a concrete size 1 n 105, they want you to compute the number of permutations on a set of cardinality n that are not idempotent.

Input

   The input starts with the number t 100 of test cases. Then t lines follow, each containing the set’s size 1 n 105.

Output

   Output one line for every test case containing the number modulo 1 000 000 007 = (109 + 7) of non-idempotent permutations on a set of cardinality n.

Examples

stdin

stdout

1

 3

 1

 2

 2171

 0

 1

 6425


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.German (GCPC) 2014.A

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.