Репликанты были созданы, чтобы выполнять работу, которую люди не хотят выполнять сами. Это включает и очень опасные миссии, которых после событий «Бегущего по лезвию 2049» становится все больше и больше.
Всего в полиции Лос-Анджелеса $$$n$$$ сотрудников, имеющих строгую иерархию. Во главе стоит новый управляющий полицией, пришедший на замену лейтенанту Джоши — сотрудник номер $$$1$$$, а остальные $$$n - 1$$$ сотрудников — репликанты, у каждого из которых есть непосредственный руководитель $$$p_i < i$$$. Таким образом, структура иерархии сотрудников представляет собой подвешенное дерево с корнем в вершине номер $$$1$$$.
Также у каждого сотрудника есть специальность $$$a_i$$$, характеризующаяся английской буквой от 'a' до 'z' — она задает навык или умение, которым соответствующий сотрудник владеет лучше всего. Известно, что специальности распределены случайно и равновероятно, то есть вероятность каждого сотрудника иметь какую-то конкретную специальность равна в точности $$$\frac{1}{26}$$$ и не зависит от специальностей других сотрудников.
Сейчас у полиции есть $$$m$$$ критически важных миссий, которыми им надо заняться в срочном порядке. Так как миссии серьезные, нельзя отправить кого угодно на их выполнение:
Для каждой из $$$m$$$ миссий найдите число способов выбрать последовательность сотрудников полиции, которое можно отправить на ее выполнение. Ответ для каждой миссии требуется найти независимо от других.
В первой строке ввода даны два целых числа $$$n$$$ и $$$m$$$ — число сотрудников полиции и миссий соответственно ($$$1 \le n, m \le 4 \cdot 10^5$$$).
Во второй строке перечислены целые числа $$$p_2, p_3, \ldots, p_n$$$ — номера непосредственных руководителей у каждого сотрудника со второго по $$$n$$$-го ($$$1 \le p_i < i$$$).
В третьей строке дана одна строка $$$a$$$ длины $$$n$$$, $$$i$$$-й из символов которой — буква от 'a' до 'z', задающая специальность $$$i$$$-го сотрудника полиции.
Затем следуют $$$m$$$ строк $$$s_i$$$, по одной в каждой строке ввода — набор специальностей, требуемый каждой миссией для ее выполнения ($$$1 \le |s_i| \le 4 \cdot 10^5$$$). Гарантируется, что каждая $$$s_i$$$ состоит только из символов от 'a' до 'z'. Также гарантируется, что суммарная длина всех $$$s_i$$$ не превосходит $$$10^6$$$.
Для каждой из $$$m$$$ миссий выведите в отдельной строке число способов выбрать $$$|s_i|$$$ сотрудников для ее выполнения, соблюдая данные в условии правила.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
0 | – | примеры из условия | полная | |
1 | 7 | $$$n, m, |s_i| \le 10$$$ | 0 | полная |
2 | 18 | $$$p_i = i - 1$$$ для всех $$$i$$$ | первая ошибка | |
3 | 8 | $$$m = 1$$$; $$$s_{i,j} = \text{'\t{a}'}$$$ для всех $$$i, j$$$ | первая ошибка | |
4 | 8 | $$$m = 1$$$ | 3 | первая ошибка |
5 | 12 | $$$|s_i| \le 3$$$ для всех $$$i$$$ | первая ошибка | |
6 | 16 | $$$n, m \le 100$$$; $$$|s_i| \le 100$$$ для всех $$$i$$$ | 0, 1 | первая ошибка |
7 | 6 | $$$n \cdot m \le 10^6$$$ | 0, 1, 6 | первая ошибка |
8 | 25 | нет | 0 – 7 | первая ошибка |
3 41 1abaaaabbabb
1 1 0 0
7 61 1 2 3 5 6aabbabaaaabbaabaababaababab
1 3 2 2 1 0
10 41 2 3 4 5 6 7 8 9abacabadababacabadabacabadababacabadabbacabadaba
1 1 1 0
Обратите внимание, что в примерах из условия нарушается условие на случайность специальностей, примеры специально подобраны для наглядности.
Во всех остальных тестах каждая специальность будет равновероятно и независимо выбрана от 'a' до 'z'.