Harary

Frank enjoys counting graphs with given properties so much that he plans to write a book about it one day. He likes to invent new complicated problems in this area, but coding the solutions is not his favorite part.

Right now, Frank is preparing many versions of a single task for an exam. He wants students to find the number of valid topological orderings of a given directed graph with $N$ nodes.

A topological ordering of a directed graph is a permutation of its vertices such that, for every arc from vertex $u_i$ to vertex $v_i$, $u_i$ comes before $v_i$ in the permutation. Two orderings are different if some vertex has different positions in the two orderings. In other words, they are different if they differ as permutations.

Frank considers the task easy if the answer is one, medium if the answer is two, and hard if the answer is three. For larger answers, he thinks the task is almost impossible to solve. He does not treat all his students equally. Some have attended every class, and some will see him for the first time at the exam. However, he does not want students to notice his small revenge, so every version has the same value of $N$.

For a fixed $N$, count how many versions of the task he could prepare for each difficulty level. Since these numbers can be very large, give them modulo $10^9 + 7$. The number of arcs can be arbitrary, but self-loops and multiple edges are not allowed.

The input contains a single integer $N$, the number of vertices ($1 \leq N \leq 100$).

Output three integers: the number of directed graphs with $N$ vertices that have exactly one, two, and three topological orderings. Give each answer modulo $10^9 + 7$.