Топологічні сортування дерева

Вам дано дерево з $n$ вершин, пронумерованих від $1$ до $n$. Корнем дерева є вершина з номером $1$. Для кожного $v$ від $2$ до $n$ визначимо $p_v$ — номер суміжної з $v$ вершини, що лежить на простому шляху між вершиною $v$ та корнем. На кожному з ребер $(p_v,v)$ записаний символ «<» або «>».

Знайдіть кількість способів записати числа від $1$ до $n$ у вершинах дерева так, щоб кожне число було використано рівно один раз і при цьому виконувались усі відношення, вказані на ребрах. Тобто для усіх ребер з символом «<» повинно виконуватись $a[p_v]<a[v]$, а для усіх ребер з символом «>» повинно виконуватись $a[p_v]>a[v]$.

Через те, що відповідь може бути дуже великою, виведіть її за модулем $10^9+7$.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 3000$) — кількість вершин дерева.

Кожен з наступних $n-1$ рядків містить одне ціле число $p_i$ ($1\le p_i<i$) та символ $c_i$ ($c_i\in \{$«<», «>»$\}$), які позначають, що на ребрі між вершинами з індексами $p_i$ та $i$ записаний символ $c_i$. Зверніть увагу, що тут нумерація за $i$ починається з $2$.

Вихідні дані

Виведіть єдине ціле число — кількість способів розставити усі числа від $1$ до $n$ у вершинах дерева так, щоб виконувались усі відношення, вказані на ребрах. Зверніть увагу, що потрібно вивести не саму відповідь, а лише її остачу від ділення на $10^9+7$.

Приклади

Оцінювання

1. ($8$ балів) $n\le 10$;

2. ($6$ балів) $n\le 18$;

3. ($10$ балів) $c_i=$ '<';

4. ($4$ бали) $p_i=1$;

5. ($13$ балів) $p_i=i-1,1\le n\le 200$;

6. ($19$ балів) $p_i=i-1$;

7. ($24$ бали) $n\le 200$;

8. ($16$ балів) без додаткових обмежень.