Frank 非常喜欢计算具有特定性质的图，以至于他甚至计划有一天为此写一本书。他喜欢在这一领域发明复杂的新问题，然而，编写这些问题的解法并不是他最喜欢的部分。

目前，Frank 正在为一场考试准备同一个任务的多个版本。他希望学生们能够求出一个给定的 $N$ 个节点的有向图的有效拓扑排序的数量。

有向图的拓扑排序是其顶点的一个排列，使得对于每一条从顶点 $u_i$ 到顶点 $v_i$ 的弧，$u_i$ 在排列中都出现在 $v_i$ 之前。如果两个排序中存在某个顶点所处的位置不同，则认为这两个排序是不同的；换句话说，如果它们作为排列不同，则它们是不同的。

Frank 认为，如果答案为 1，则该任务是简单的；如果答案为 2，则是中等的；如果答案为 3，则是困难的。对于更大的答案，他认为该任务几乎无法解决。他对待学生也不一视同仁，因为有些学生上过所有的课，而有些学生则是第一次在考试中见到他。然而，他不想让学生察觉到他的这点“小报复”，所以每个人的任务版本中 $N$ 的值都是相同的。

现在 Frank 请你计算，对于固定的 $N$，他可以为每个难度等级准备多少个任务版本。由于这些数字可能非常大，Frank 希望得到它们对 $10^9 + 7$ 取模后的结果。注意，弧的数量可以是任意的，但不允许存在自环和重边。

输入格式

输入包含一个整数 $N$，表示顶点的数量 ($1 \le N \le 100$)。

输出格式

输出三个整数：具有 $N$ 个顶点且恰好有 1 个、2 个和 3 个拓扑排序的有向图的数量。请将答案对 $10^9 + 7$ 取模。

样例

样例输入 1

3

样例输出 1

12
6
6