Problem description

Jasio dowiedział się właśnie czym są grafy eulerowskie: są to takie grafy, w których istnieje cykl Eulera tzn. cykl przechodzący po wszystkich krawędziach dokładnie raz.

Zastanawia się teraz ile jest grafów eulerowskich na N wierzchołkach. Pomóż mu!

Jasio rozważa tylko spójne nieskierowane grafy proste tzn. nie zawierające pętli (krawędzi od wierzchołka do siebie samego) i nie zawierające wielokrotnych krawędzi pomiędzy tą samą parą wierzchołków.

Dwa grafy o tej samej liczbie wierzchołków uznajemy za różne, jeśli zbiory ich krawędzi są różne (krawędź utożsamiamy z dwuwierzchołkowym zbiorem wierzchołków). Wierzchołki etykietowane są kolejnymi liczbami naturalnymi od 1 do N włącznie.

Napisz program, który wczyta liczbę naturalną N, wyznaczy liczbę N-wierzchołkowych grafów eulerowskich i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N – liczba wierzchołków grafu.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać resztę z dzielenia przez 10⁹ + 7 liczby eulerowskich grafów prostych rozpiętych na N wierzchołkach.

Ograniczenia

1 ≤ N ≤ 5 000.

Przykład

4

3