Задача . E. Отправьте дерево Чарли

Рождество постучало в дверь, и наш главный герой, Боб, готовил захватывающий подарок для своего давнего второго лучшего друга Чарли. Поскольку ему не нравится шоколад, он решил вместо этого украсить дерево. Дерево Боба можно представить в виде неориентированного связного графа с \(n\) вершинами (пронумерованными от \(1\) до \(n\)) и \(n-1\) ребрами. Первоначально Боб поместил украшение с номером \(i\) на вершину \(i\) для каждого \(1 \le i \le n\). Однако, поскольку такая простая композиция получилась некрасивой, он решил немного переместить украшения. Формально Боб сделал следующие шаги:

• Сначала он выписал все \(n-1\) ребра в некотором порядке.
• Затем он рассмотрел все ребра один за другим в таком порядке. Для каждого ребра \((u, v)\) он поменял местами украшение вершины \(u\) с украшением вершины \(v\).

После этого Боб оказался довольным такой аранжировкой и пошел спать.

На следующее утро Боб просыпается, только чтобы узнать, что его прекрасная аранжировка разрушена! Прошлой ночью младший брат Боба, Бобо, бросил некоторые украшения на пол, когда играл с деревом. К счастью, украшения не были потеряны, поэтому Боб может восстановить дерево в кратчайшие сроки. Однако он полностью забыл, как дерево выглядело вчера. Поэтому, учитывая номера украшений, которые все еще на дереве, Боб хочет узнать количество возможных конфигураций дерева. Поскольку результат может быть довольно большим, Боб будет рад, если вы сможете вывести результат по модулю \(1000000007\) (\(10^9+7\)). Обратите внимание, что, возможно, не существует никаких возможных конфигураций.