Топологічні сортування дерева#260
Вам дано дерево з вершин, пронумерованих від до . Корнем дерева є вершина з номером . Для кожного від до визначимо p_v — номер суміжної з вершини, що лежить на простому шляху між вершиною та корнем. На кожному з ребер (p_v, v) записаний символ «<» або «>».
Знайдіть кількість способів записати числа від до у вершинах дерева так, щоб кожне число було використано рівно один раз і при цьому виконувались усі відношення, вказані на ребрах. Тобто для усіх ребер з символом «<» повинно виконуватись a[p_v] < a[v], а для усіх ребер з символом «>» повинно виконуватись a[p_v] > a[v].
Через те, що відповідь може бути дуже великою, виведіть її за модулем 10^9 + 7.
Перший рядок містить одне ціле число (1 \leq n \leq 3\,000) — кількість вершин дерева.
Кожен з наступних n-1 рядків містить одне ціле число p_i (1 \leq p_i < i) та символ c_i (c_i \in \{«<», «>»), які позначають, що на ребрі між вершинами з індексами p_i та записаний символ c_i. Зверніть увагу, що тут нумерація за починається з .
Виведіть єдине ціле число — кількість способів розставити усі числа від до у вершинах дерева так, щоб виконувались усі відношення, вказані на ребрах. Зверніть увагу, що потрібно вивести не саму відповідь, а лише її остачу від ділення на 10^9 + 7.
Приклад
Приклад 1
Приклад 2
( балів) n \leq 10;
( балів) n \leq 18;
( балів) c_i = '<';
( бали) p_i = 1;
( балів) p_i = i - 1, 1 \leq n \leq 200;
( балів) p_i = i - 1;
( бали) n \leq 200;
( балів) без додаткових обмежень.