Ямка и Ямочка являются огромными любителями кооперативных настольных игр. Они способны играть в них дни напролет, но бывают моменты, когда становится немного скучно. Вот, например, сейчас Ямка и Ямочка вместе собрались исследовать подземелье, однако на входе в данж обнаружилась головоломка, которую необходимо решить, чтобы пройти дальше. Ямка, как большой фанат и бывалый любитель загадок, сразу принялся решать ее с помощью своей инновационной методики подбора решения к любой задаче, именуемой методом тыка!

К сожалению, решение загадок — процесс небыстрый, и Ямочке он мало интересен, поэтому, чтобы хоть как-то себя занять, она решила тщательнее обдумать план исследования подземелья, а именно выбрать лучший порядок зачистки комнат. Подземелье представляет собой N комнат, некоторые пары которых соединены тоннелями, по которым можно свободно перемещаться между комнатами, причем в обоих направлениях. Также из любой комнаты по тоннелям достижима любая другая, и всего в подземелье N−1 тоннель. Более формально, подземелье является неориентированным деревом. Зачистка подземелья происходит так: вначале Ямка и Ямочка телепортируются в любую комнату на их выбор и зачищают ее, после чего действуют по следующему алгоритму, пока все комнаты не станут зачищенными:

Пару часов назад, когда герои собирали вещи для похода в подземелье, они нашли последовательность целых чисел p длины N. Не найдя ей применения ранее, Ямочка решила использовать ее сейчас, а конкретнее, она решила, что они будут зачищать комнаты в таком порядке, чтобы последовательность, в которой зачищались комнаты, не была лексикографически больше последовательности p. Последовательность a лексикографически больше последовательности b, если существует такой индекс i (1 ≤ i ≤ N), что для любого j (1 ≤ j < i) a_j=b_j и a_i>b_i. Теперь Ямочке интересно, сколько существует различных подходящих последовательностей зачистки комнат.

В первой строке дано целое число N (1 ≤ N ≤ 10⁵).

В следующих N − 1 строках даются по два целых числа x_i, y_i — пара комнат, между которыми есть тоннель. Гарантируется, что тоннели и комнаты подземелья образуют дерево.

В последней строке дана последовательность целых чисел p длины N (1 ≤ p_i ≤ N).

Посчитайте количество различных подходящих последовательностей зачистки комнат. Так как это число может быть достаточно большим, выведите его остаток при делении на 952426967.