Lukas is a Civil Engineer who loves designing road networks to connect cities numbered from to . He can build any number of bidirectional roads as long as the resultant network satisfies these constraints:
It must be possible to reach any city from any other city by traveling along the network of roads.
No two roads can directly connect the same two cities.
A road cannot directly connect a city to itself.
In other words, the roads and cities must form a simple connected labeled graph.
You must answer queries, where each query consists of some denoting the number of cities Lukas wants to design a bidirectional network of roads for. For each query, find and print the number of ways he can build roads connecting cities on a new line; as the number of ways can be quite large, print it modulo .
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains an integer denoting the value of for a query.
For each of the queries, print the number of ways Lukas can build a network of bidirectional roads connecting cities, modulo , on a new line.
Sample Input 0
Sample Output 0
We answer the first two queries like this:
When , the only option satisfying Lukas' three constraints is to not build any roads at all. Thus, we print the result of on a new line.
When , there are four ways for Lukas to build roads that satisfy his three constraints: