Дерево з щасливими цифрами
Обмеження: 2 сек., 256 МіБ
У Зеника є кореневе дерево, у кожній вершині якого записано по одній щасливій цифрі 4 або 7.
Допоки у дереві є хоча б одна вершина із цифрою 7, послідовно виконується наступний крок: випадковим чином вибирається довільна вершина дерева, і в усіх вершинах її піддерева щаслива цифра змінюється на протилежну (4 на 7 або навпаки).
Допоможіть Зенику порахувати очікувану кількість кроків, яку буде виконано.
Вхідні дані
У першому рядку задано одне ціле число \(n\) — кількість вершин дерева.
У другому рядку задано \(n\) чисел \(a_i\) — початкові щасливі цифри, записані на вершинах дерева.
У останньому рядку задано \(n - 1\) число \(p_i\) (\(2 \le i \le n, p_i < i\)) — номер батька вершини \(i\) у дереві. Для першої вершини немає батька, бо вона є коренем дерева.
Вихідні дані
Неважко показати, що відповідь завжди можна представити у вигляді дробу \(\frac{a}{b}\). У єдиному рядку виведіть одне ціле число — \(a \cdot b^{-1}\) по модулю \(10^9 + 7\).
Обмеження
\(2 \le n \le 200\),
\(a_i \in \{4, 7\}\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 4 7 1 | 3 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 4 4 7 1 2 | 7 |
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|