Те, кто не хотят возвращаться домой из дальнего путешествия, будут поражены болезнью улитки и потеряются. Майои, переносчик болезни, не хочет, чтобы такое случалось, но не может ничем помочь до того, как найдется лекарство. Сейчас она лишь хочет узнать, насколько сложно придется потерявшемуся.

В регионе находятся n городов, пронумерованных от 1 до n, город номер 1 является столицей. Сеть дорог образована двусторонними дорогами равной длины, каждая из которых соединяет два города. Никакие две дороги не соединяют одинаковые пары городов, и никакая дорога не соединяет город сам с собой. Потерявшиеся не могут узнать, как устроена сеть, но жители могут предоставить следующую информацию:

• Из любого города существует ровно один кратчайший (по числу дорог) путь до столицы;
• Пусть расстояние от города i до столицы равно l_i. Тогда l_i ≥ l_i - 1 выполняется для всех 2 ≤ i ≤ n;
• К городу i подходит ровно d_i дорог, и это число равно либо 2, либо 3.

Подсчитайте, сколько различных сетей дорог существует с заданными ограничениями и выведите ответ по модулю 10⁹ + 7. Две сети считаются различными, если есть пара (u, v) (1 ≤ u, v ≤ n) такая, что в одной сети есть дорога между городами u и v, а в другой такой дороги нет.