All submissions for this problem are available.
Digo loves graphs. He defines a super-connected graph as a graph having N nodes, such that for any j, 1<=j<=N-1, it is possible to reach from node 1 to node j without crossing nodes j+1 to N.
The magician Gogo has decided to take over the world. The only man who stands between him and total world annihilation is Digo. Gogo knows that Digo does not stand a chance against his magical skills. He however believes that every great villain needs a great hero. Therefore he decides to give Digo one last chance to save the world. Knowing Digo's love for graphs, magician Gogo hands over Digo his magical scroll and gives him a chance to destroy it. Gogo etches an N-Magic graph on the scroll using his magic wand. The magical scroll can only be destroyed if Digo draws on it, the exact same graph.
An N-Magic Graph is defined as a graph having N nodes, such that for any given j, 1<=j<=N, it is possible to draw the graph remaining after removing all nodes from j+1 to N and all the edges touching these nodes, on the magical scroll without lifting the wand.
Digo however has no idea what an N-Magic Graph means, and being the sly opponent that he is, Gogo has no intentions of telling this to Digo as well. Thus, Digo plays a mathematical gamble and using Gogo's magic wand, draws a Super-Connected Graph having N nodes on the scroll.
Let the graph drawn by magician Gogo be G1 and that drawn by Digo be G2. A graph combination is thus the ordered pair (G1, G2). Two graph combinations (G1, G2) and (G3, G4) are said to be the same if G1 is the same as G3 and G2 is the same as G4.
Clearly the probability of Digo destroying the scroll and saving the world is given by S/M, where M is the number of different Graph combinations and S is the number of different graph combinations (G1,G2) where G1 is the same as G2.
Your task is to determine M modulo 1000000007.
The first line contains T, the number of test cases.
T lines follow, each containing one positive integer N.
Output one line per test case, which contains the required answer.
1 <= T <= 105
1 <= N <= 106
|Time Limit:||0.199616 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.