Дерево з щасливими цифрами
Limits: 2 sec., 256 MiB
У Зеника є кореневе дерево, у кожній вершині якого записано по одній щасливій цифрі 4 або 7.
Допоки у дереві є хоча б одна вершина із цифрою 7, послідовно виконується наступний крок: випадковим чином вибирається довільна вершина дерева, і в усіх вершинах її піддерева щаслива цифра змінюється на протилежну (4 на 7 або навпаки).
Допоможіть Зенику порахувати очікувану кількість кроків, яку буде виконано.
Input
У першому рядку задано одне ціле число nn — кількість вершин дерева.
У другому рядку задано nn чисел aiai — початкові щасливі цифри, записані на вершинах дерева.
У останньому рядку задано n−1n−1 число pipi (2≤i≤n,pi<i2≤i≤n,pi<i) — номер батька вершини ii у дереві. Для першої вершини немає батька, бо вона є коренем дерева.
Output
Неважко показати, що відповідь завжди можна представити у вигляді дробу abab. У єдиному рядку виведіть одне ціле число — a⋅b−1a⋅b−1 по модулю 109+7109+7.
Constraints
2≤n≤2002≤n≤200,
ai∈{4,7}ai∈{4,7}.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 2 4 7 1 | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 3 4 4 7 1 2 | 7 |