Problem description

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Grafy eulerowskie (grafy-eulerowskie) Limit pamięci: 32 MB Limit czasu: 1.50 s 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 109 + 7 liczby eulerowskich grafów prostych rozpiętych na N wierzchołkach. Ograniczenia 1 ≤ N ≤ 5 000. Przykład Wejście Wyjście 4 3