0379. Фермерское чтиво

Имя входного файла:	tree.in
Имя выходного файла:	tree.out
Ограничение по времени:	2 s
Ограничение по памяти:	256 megabytes

Егор – очень почетный фермер. Довольные покупатели прозвали его <<Пышный>>. Секрет его успеха, конечно же лежит в его манере управлять фермой. Например, у него организована строгая иерархия среди всего скота.

Более конкретно, всего в подчинении Егора находится N - 1 скотина с номерами от 2 до N, Егор не любит отбиваться от коллектива, поэтому тоже имеет номер -- 1. У каждой скотины есть непосредственный начальник, причем ровно один. Начальником может быть либо другая скотина, либо сам Егор.

Недавно Егор решил постричь тех скотин, у которых нет подчиненных. Для начала ему нужно составить порядок в котором он будет их стричь. Однако, появилось некоторое затруднение. Чтобы никого не обидеть, Егор должен учесть M требований вида: скотина, которую Егор будет стричь a_i-м по счету, должна находиться в подчинении (не обязательно прямом) скотины с номером b_i (при этом в требовании b_i может оказаться номер скотины без подчиненных, это значит, что именно эту скотину нужно стричь a_i-й по счету).

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

Формат входного файла

Первая строка входного файла содержит два целых числа N и M (2 ≤ N ≤ 3 *10⁵, 0 ≤ M ≤ 3 *10⁵) – количество скотин и количество требований, соответственно. Скотина с номером 1 – Егор. В каждой i-й строке из последующих N - 1 строк находится единственное число 1 ≤ p_i < i + 1 – начальник скотины с номером i + 1. В каждой i-й строке из последующих M строк находится по два числа 1 ≤ a_i, b_i ≤ 3 *10⁵ – скотина, которую будут стричь a_i-й, должна находится в подчинении (не обязательно прямом) скотины с номером b_i. Гарантируется, что a_i не превосходит количества скотин без подчиненных. Также номер b_i может принадлежать скотине без подчиненных, это означает, что эту скотину нужно стричь a_i-й по счету.

Формат выходного файла

В выходной файл выведите единственное число – количество различных способов стрижки по модулю 10⁹ + 7.

Пример:

tree.in	tree.out
5 3 1 1 2 2 1 2 2 1 3 2	2
6 1 1 1 2 2 2 4 3	6

В первом примере требуется постричь скотин с номерами 3, 4 и 5. При этом скотины 4 и 5 находятся в подчинении у скотины номер 2 и при этом все скотины прямо или косвенно подчиняются Егору. Требования говорят, что в первую и третью очередь нужно стричь подчиненных номера 2. Таким образом мы можем либо в первую очередь стричь четвёртого, в третью пятого, либо наоборот. Третьего же остаётся стричь только во вторую очередь. Таким образом получаем два возможных порядка стрижки: 4 3 5 и 5 3 4.

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати