거의 오일러 그래프

정점이 $N$개인 양방향 그래프가 있다. 정점에는 $0$번부터 $N-1$번까지 번호가 매겨져 있다. 이 그래프는 단순 그래프이므로 루프가 없고, 두 정점을 잇는 간선은 많아야 한 개다.

연결 그래프이면서 모든 간선을 정확히 한 번씩 지나는 닫힌 보행이 존재하면, 그 그래프를 오일러 그래프라고 한다. 닫힌 보행은 첫 정점과 마지막 정점이 같은 보행이다. 연결 그래프라는 조건은 정점 $N$개가 모두 한 덩어리로 이어져 있어야 한다는 뜻이다.

어떤 그래프에 간선 한 개를 추가하거나 한 개를 제거해서 오일러 그래프를 만들 수 있으면, 그 그래프를 거의 오일러 그래프라고 한다. 간선을 추가할 때 루프를 만들거나 이미 있는 간선을 다시 추가할 수는 없다. 또 모든 오일러 그래프는 거의 오일러 그래프다.

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

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

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