26524번 - 방향 정하기

$n$개의 점이 있다. 어떤 두 점을 잡더라도 항상 하나의 간선으로 이어져 있도록 간선이 총 $\frac{n(n-1)}{2}$개 있다.

조건을 만족하도록 모든 간선들에 방향을 정해주는 방법의 수를 구하자.

• 조건: 각 점에서 출발해서 간선 방향을 따라 어떻게 이동해도 출발한 점으로 돌아올 수 없다.

첫 번째 줄에 $n$이 주어진다. $(2 \leq n \leq 1\,000\,000)$

조건을 만족하는 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.