Джон только что купил новую машину и планирует поездку по стране. В стране N городов, некоторые из них соединены двусторонними дорогами. В стране N - 1 дорог и из каждого города можно попасть в любой другой город. Города пронумерованы от 1 до N.

Сначала Джон выбирает, из какого города он начнёт своё путешествие. После этого он проводит один день в городе, после чего он едет к случайно выбранному городу, к которому есть прямая дорога из нынешнего местоположения Джона и который он ещё не посещал. Он делает так, пока следование данным правилам не становится невозможным.

Чтобы выбрать город, с которого он начнёт своё путешествие, он обращается к своему другу Джеку за советом. Джек хочет попасть в большой игорный бизнес, поэтому он хочет открыть казино в некоторых городах (не больше 1 в каждом городе, может не открыть ни одного нигде). Джек знает Джона достаточно хорошо, чтобы знать, что при своём посещении города с казино Джон зайдёт в него ровно один раз перед тем, как продолжить путешествие.

Также он знает, что если Джон зайдёт в казино с хорошим настроением, он выйдет из него с плохим, и наоборот. Так как Джек — друг Джона, он хочет, чтобы по окончанию путешествия Джон был в хорошем настроении. В начале путешествия Джон в хорошем настроении.

Сколькими способами Джек может выбрать начальный город для Джона и города, в которых он построит казино так, чтобы вне зависимости от того, как Джон будет путешествовать, он окажется в хорошем настроении по окончании путешествия? Выведите ответ по модулю 10⁹ + 7.