Codeforces Round 263 (Div. 1) |
---|
Закончено |
У Яблова есть дерево, состоящее из n вершин. Некоторые вершины (по крайней мере одна) покрашены в черный цвет, остальные вершины покрашены в белый цвет.
Рассмотрим множество, состоящее из k (0 ≤ k < n) ребер этого дерева. Если Яблов удалит эти ребра из дерева, то дерево распадется на (k + 1) частей. Каждая часть также будет представлять из себя дерево с покрашенными вершинами.
Теперь Яблову интересно, сколько существует множеств, в результате удаления ребер которых в каждой получившейся части будет ровно одна черная вершина? Выведите это количество по модулю 1000000007 (109 + 7).
В первой строке записано целое число n (2 ≤ n ≤ 105) — количество вершин дерева.
Во второй строке содержится описание дерева: n - 1 целых чисел p0, p1, ..., pn - 2 (0 ≤ pi ≤ i). Где pi означает, что существует ребро, соединяющее вершину (i + 1) и вершину pi дерева. Считайте, что вершины дерева пронумерованы от 0 до n - 1.
В третьей строке записано описание раскраски вершин дерева: n целых чисел x0, x1, ..., xn - 1 (xi равняется либо 0, либо 1). Если xi равняется 1, вершина i покрашена в черный цвет. В противном случае, вершина i покрашена в белый цвет.
Выведите единственное целое число — количество требуемых множеств по модулю 1000000007 (109 + 7).
3
0 0
0 1 1
2
6
0 1 1 0 4
1 1 0 0 1 0
1
10
0 1 2 1 4 4 4 0 8
0 0 0 1 0 1 1 0 0 1
27
Название |
---|