Hamilton Path

A directed graph has $n$ vertices and $m$ edges. The vertices are labeled from $1$ to $n$. Find all permutations $p_1, p_2, \ldots, p_n$ of the vertices that satisfy the following constraint.

• For all $1 \leq i < j \leq n$, the edge $(p_i, p_j)$ exists if and only if $j = i + 1$.

The value of a permutation $p_1, p_2, \ldots, p_n$ is $\left(\sum_{i = 1}^n p_i \cdot 10^{n - i}\right) \bmod (10^9 + 7)$.

Output the number of such permutations modulo $10^9 + 7$. If the number of such permutations is at most $n$, also list their values in the lexicographical order of the permutations.

The first line contains an integer $T$ ($T \leq 10^5$), the number of test cases.

For each test case, the first line contains two integers $n$ and $m$ ($n \geq 1$, $m \geq 0$, $1 \leq \sum n \leq 5 \cdot 10^5$, $1 \leq \sum m \leq 10^6$). Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \leq u, v \leq n$, $u \neq v$), meaning there is a directed edge from $u$ to $v$. The graph may contain parallel edges.

For each test case, print the number of permutations modulo $10^9 + 7$ on the first line. If the number of permutations is at most $n$, print another line with the values of all the permutations, separated by spaces, in lexicographical order of the permutations. If the number is greater than $n$ or there is no solution, you do not need to print the empty line.