28767번 - Доставка почты 다국어

Для автоматизированной доставки почты в отдалённых регионах тестируется роботизированная система с использованием автоматизированного робота-курьера.

В регионе расположены $n$ городов, соединённые $n - 1$ двусторонними дорогами. По дорогам можно добраться от каждого города до любого другого. Если два города соединены дорогой, назовём их соседними. У каждого города не более $D$ соседних городов. Города пронумерованы от $1$ до $n$, город номер $1$ является столицей региона.

В каждом городе находится офис курьерской компании. Курьеру необходимо развезти $m$ посылок. Для $i$-й посылки заданы два числа: $a_i$ и $b_i$ --- город, из которого надо доставить посылку, и город, в который надо доставить посылку.

Робот-курьер действует по следующему алгоритму.

• Он начинает свой путь в столице и перемещается между городами по дорогам. При перемещении между городами курьер может перевозить на себе произвольное число посылок.
• Каждый раз, когда курьер приезжает в город, в котором он ранее не был, он заезжает в офис, находящийся в этом городе, оставляет все имеющиеся у него посылки, адресованные в этот город, и забирает все посылки, отправляемые из этого города.
• Если есть соседний с текущим город, в котором курьер ещё не был, он выбирает один из этих городов и перемещается в него.
• Если все соседние города посещены, и курьер находится не в столице, он перемещается в соседний город, ближайший к столице. Если курьер находится в столице, он прекращает свою поездку.

Обратите внимание, что курьер заезжает в офис в каждом городе ровно один раз, при первом посещении. Курьер доставит $i$-ю посылку, если он заедет в офис в $a_i$-м городе раньше, чем в офис в $b_i$-м городе.

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

Требуется написать программу, которая по заданному описанию дорог в регионе и посылок, которые необходимо доставить, определяет количество различных допустимых последовательностей посещения городов и выводит остаток от деления этого количества на $10^9+7$.

В первой строке даны два целых числа $n$ и $m$ --- количество городов в регионе и количество посылок ($2 \le n \le 100\,000$, $1 \le m \le 300\,000$).

В следующих $n - 1$ строке даны описания дорог. Каждая дорога описывается двумя целыми числами $u_i$ и $v_i$ --- номера городов, которые соединяет $i$-я дорога ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

Гарантируется, что по дорогам можно добраться от любого города до любого другого. Гарантируется, что количество дорог, выходящих из каждого города, не превосходит $D$.

В следующих $m$ строках даны описания посылок. Каждая посылка описывается двумя целыми числами $a_i$ и $b_i$ --- номера городов, из которого и в который нужно доставить $i$-ю посылку ($1 \le a_i, b_i \le n$, $a_i \ne b_i$).

В единственной строке выведите одно целое число --- ответ по модулю $10^9+7$.

Рассмотрим схему городов и дорог из первого примера, она приведена на рисунке. Необходимо доставить посылки из города 5 в город 3 и из города 4 в город 6.

Следующие последовательности посещения городов являются допустимыми. Первое посещение, во время которого курьер посещает офис, отмечено жирным: $(\mathbf{1}, \mathbf{4}, 1, \mathbf{2}, \mathbf{5}, 2, \mathbf{6}, 2, 1, \mathbf{3}, 1)$, $(\mathbf{1}, \mathbf{4}, 1, \mathbf{2}, \mathbf{6}, 2, \mathbf{5}, 2, 1, \mathbf{3}, 1)$.

Во втором примере для той же схемы городов и дорог необходимо доставить посылку из города 5 в город 2. Это невозможно, так как при повторном посещении города 2 курьер не заезжает в офис, а впервые посетить город 5 до города 2 при пути из столицы невозможно.