Harary

프랭크는 주어진 성질을 가진 그래프를 세는 것을 매우 좋아해서, 언젠가 이 주제로 책을 쓸 계획도 있다. 그는 이 분야에서 새롭고 복잡한 문제를 만들어 내는 것을 좋아하지만, 풀이를 코드로 작성하는 일은 그리 좋아하지 않는다.

프랭크는 지금 시험에 낼 하나의 과제에 대한 여러 버전을 준비하고 있다. 그는 학생들이 $N$개의 정점을 가진 방향 그래프의 유효한 위상 정렬 개수를 구하기를 원한다.

방향 그래프의 위상 정렬은 정점들의 순열이다. 모든 간선 $u_i \to v_i$에 대해 $u_i$가 순열에서 $v_i$보다 앞에 와야 한다. 두 정렬은 어떤 정점의 위치가 두 정렬에서 다르면 서로 다른 것으로 본다. 즉 순열로서 다르면 다른 정렬이다.

프랭크는 정답이 1이면 쉬운 과제, 2이면 보통 과제, 3이면 어려운 과제로 본다. 정답이 더 크면 풀기 거의 불가능하다고 여긴다. 그는 학생을 모두 같게 대하지 않는다. 수업에 빠짐없이 나온 학생도 있고, 시험에서 처음 그를 만나는 학생도 있다. 다만 자신의 작은 복수를 학생들이 눈치채지 않기를 바라므로, 모든 버전의 $N$ 값은 같게 한다.

고정된 $N$에 대해, 각 난이도별로 프랭크가 준비할 수 있는 과제 버전의 개수를 구하라. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구한다. 간선의 개수는 임의로 정해질 수 있으나, 자기 루프와 중복 간선은 허용되지 않는다.

정점의 개수 $N$이 한 정수로 주어진다. ($1 \leq N \leq 100$)

세 정수를 출력한다. 정점이 $N$개인 방향 그래프 중 위상 정렬이 정확히 1개, 2개, 3개인 그래프의 개수를 차례로 출력한다. 각 답은 $10^9 + 7$로 나눈 나머지이다.