|
Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.
Деревья ограничение по времени на тест 2 секундыограничение по памяти на тест 64 мегабайтаввод стандартный вводвывод стандартный выводДеревом называется граф, содержащий N вершин и (N - 1) рёбер. На рисунке ниже показаны все типы деревьев, содержащих две или три вершины. Сколько существует различных деревьев, содержащих N вершин? Входные данные Единственная строка содержит одно целое число N (2 ≤ N ≤ 105) — количество вершин. Выходные данные Выведите одно число — количество различных деревьев, содержащих N вершин. Так как это число может оказаться очень большим, выведите остаток от его деления на 1000000007. Примеры тестов Входные данные 2 Выходные данные 1 Входные данные 4 Выходные данные 16 |