C. Разбиение на регионы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В королевстве Осени $$$n$$$ городов, пронумерованных от $$$1$$$ до $$$n$$$. От любого города можно добраться до любого другого, используя некоторые из $$$n-1$$$ дорог в королевстве.

В этом году правительство приняло решение разбить королевство на регионы. После разбиения будут существовать регионы нескольких уровней, при этом само королевство будет являться регионом первого уровня. Любой регион уровня $$$i$$$ должен быть разделен на несколько (хотя бы два) регионов уровня $$$i+1$$$, если это не регион последнего уровня. Каждый город должен принадлежать ровно одному региону каждого уровня. Внутри одного региона, между любыми двумя городами в нем должен существовать путь, проходящий только по городам этого региона.

Согласно исследованию, для каждого города $$$i$$$ есть уровень важности — $$$a_i$$$. Все регионы одного уровня должны иметь одинаковую сумму этих значений.

Ваша задача состоит в том, чтобы узнать, сколько существует планов разбиения королевства на регионы, чтобы все условия выполнялись. Два плана считаются различными тогда и только тогда, когда количество уровней в них различно, или существует пара городов, которые для какого-то уровня находятся в одном регионе в одном плане, но в разных регионах того же уровня в другом. Поскольку ответ может быть очень большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

Первая строка содержит число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — количество городов в королевстве.

Вторая строка содержит $$$n$$$ чисел, $$$i$$$-е из которых обозначает $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — важность $$$i$$$-го города.

В третьей строке записано $$$n-1$$$ целое число, $$$p_1, p_2, \ldots, p_{n-1}$$$; $$$p_i$$$($$$p_i \leq i$$$) описывает дорогу между городами $$$p_i$$$ и $$$i+1$$$.

Выходные данные

Выведите одно число — количество различных планов по модулю $$$10^9+7$$$.

Примеры
Входные данные
4
1 1 1 1
1 2 3
Выходные данные
4
Входные данные
4
1 1 1 1
1 2 2
Выходные данные
2
Входные данные
4
1 2 1 2
1 1 3
Выходные данные
3
Примечание

В первом примере существует $$$4$$$ различных плана:

План $$$1$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$.

План $$$2$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$, Уровень $$$2$$$: $$$\{1,2\}$$$,$$$\{3,4\}$$$.

План $$$3$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$, Уровень $$$2$$$: $$$\{1\}$$$,$$$\{2\}$$$,$$$\{3\}$$$,$$$\{4\}$$$.

План $$$4$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$, Уровень $$$2$$$: $$$\{1,2\}$$$,$$$\{3,4\}$$$, Уровень $$$3$$$: $$$\{1\}$$$,$$$\{2\}$$$,$$$\{3\}$$$,$$$\{4\}$$$.

Во втором примере существует $$$2$$$ различных плана:

План $$$1$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$.

План $$$2$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$, Уровень $$$2$$$: $$$\{1\}$$$,$$$\{2\}$$$,$$$\{3\}$$$,$$$\{4\}$$$.

В третьем примере существует $$$3$$$ различных плана:

План $$$1$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$.

План $$$2$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$, Уровень $$$2$$$: $$$\{1,2\}$$$,$$$\{3,4\}$$$.

План $$$3$$$: Уровень $$$1$$$: $$$\{1,2,3,4\}$$$, Уровень $$$2$$$: $$$\{1,3\}$$$,$$$\{2\}$$$,$$$\{4\}$$$.