N개의 정점으로 이루어져있는 양방향 그래프가 있다. 그래프의 정점은 0번부터 N-1번까지 번호가 매겨져 있다. 이 그래프는 단순 그래프이기 때문에, 루프를 포함하지 않으며, 임의의 두 정점을 연결하는 간선의 개수는 최대 1개이다.</p>

그래프의 모든 간선을 포함하는 닫힌 보행이 존재할 때, 그러한 양방향 연결 그래프를 오일러 그래프라고 한다. 여기서 닫힌 보행이란, 첫 정점과 마지막 정점이 같은 보행을 의미한다.

어떤 그래프가 있을 때, 이 그래프에 간선 1개를 추가하거나 제거했을 때, 결과 그래프가 오일러 그래프가 되었다면, 이 그래프를 거의 오일러 그래프라고 한다. 간선을 추가할 때, 루프를 만들거나 이미 존재하는 간선을 또 추가할 수는 없다. 또, 모든 오일러 그래프는 거의 오일러 그래프이다.

N이 주어졌을 때, 정점이 N개인 서로 다른 거의 오일러 그래프의 개수를 구하는 프로그램을 작성하시오. 0 ≤ i < j ≤ N-1을 만족하는 간선 (i, j)가 한 그래프에는 존재하는데, 다른 그래프에는 존재하지 않는다면, 두 그래프를 다른 그래프라고 한다.

입력 형식

첫째 줄에 정점의 개수 N (2 ≤ N ≤ 2000)이 주어진다. 

출력 형식

첫째 줄에 정점 N개로 이루어진 거의 오일러 그래프의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3

예제 출력 1

4

예제 입력 2

2

예제 출력 2

0

예제 입력 3

42

예제 출력 3

29010676