- Prepare
- Algorithms
- Dynamic Programming
- Counting Road Networks

# Counting Road Networks

# Counting Road Networks

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 .

**Input Format**

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.

**Constraints**

**Output Format**

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**

```
3
1
3
10
```

**Sample Output 0**

```
1
4
201986643
```

**Explanation 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:

Thus, we print the result of on a new line.