Imagine you have \(N\) boxes labeled with unique stickers indicating what's inside. Now, You decide to be mischievous and randomly shuffle the stickers on these boxes. The challenge is to figure out the probability of exactly \(i\) boxes ending up with the correct stickers modulo \(1000000007\) after this playful (random) shuffle for each \(i\) from \(0\) to \(N\).

Note: It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction \(A/B\), then \(B\) is not divisible by \(1000000007\). Here, there is a unique integer \(C\) such that \(B×C≡A\) (mod \(1000000007\)). Report this \(C \ (0 \leq C \lt 10^9 + 7)\) for every probability value.

Input format

The first line contains a single integer \(T\), which denotes the number of test cases.
For each test case:
- A line contains a single integer \(N\) denoting the number of boxes.

Output format

For each test case, print \(N+1\) integers in a new line, where the \(i^{th}\) integer is the probability of exactly \((i-1)\) boxes ending up with the correct stickers modulo \(1000000007 \) after the playful (random) shuffle.

Constraints

\(1 \leq T \leq 10^4 \\ 1 \leq N \leq 10^6 \\ \text{The sum of all values of N over all test cases doesn't exceed } 10^6\)