Migrated from Lutece 2839 Fatdog 和他的拓扑排列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Fatdog 在学习图论，他学到了一个名词叫做拓扑排列。

一个拓扑排列的获得方式如下：

1. 选择并记录当前图中入度为 $0$ 的一个点；
2. 删掉这个点和这个点连接的边。

当图中没有节点的时候停止上述步骤，而此时我们就已经记录下一整串排列了，我们称这个排列为这个图的一个拓扑排列。

当然，有些图并不存在拓扑排列，也有一些图有不止一个拓扑排列。Fatdog 的疑问来了，有多少张有 $n$ 个点的图有一个不同的拓扑排列，有两个不同的拓扑排列，有三个不同的拓扑排列？答案对 $10^9+7$ 取模后输出。

Input

第一行一个数 $n\ (1\le n\le 100)$，代表图中有 $n$ 个点。

Output

三行三个数，代表三个答案。第 $i$ 行输出有多少张有 $n$ 个点的图有 $i$ 个不同的拓扑排列。

Samples

4

192
120
96

Resources

The 18th UESTC Programming Contest Preliminary