E. Древесно-строковая задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Корневым деревом называется неориентированный связный граф без циклов с выделенной вершиной, которая называется корнем дерева. Будем считать, что вершины корневого дерева из n вершин пронумерованы от 1 до n. В этой задаче корнем дерева будет вершина с номером 1.

Обозначим через d(v, u) длину кратчайшего по количеству ребер пути в дереве между вершинами v и u.

Родителем вершины v в корневом дереве с корнем в вершине r (v ≠ r) называется вершина pv, такая, что d(r, pv) + 1 = d(r, v) и d(pv, v) = 1. Например, на рисунке родителем вершины v = 5 является вершина p5 = 2.

Как-то раз Поликарп раздобыл корневое дерево из n вершин. Дерево было не совсем обычное — на его ребрах были написаны строки. Поликарп расположил дерево на плоскости так, что все ребра ведут сверху вниз при прохождении от родителя вершины к вершине (см. рисунок). Для каждого ребра, ведущего из вершины pv в вершину v (1 < v ≤ n), известна строка sv, которая на нем написана. Все строки записаны на ребрах сверху вниз. Например, на рисунке s7ba». Символы в строках пронумерованы от 0.

Пример дерева Поликарпа (соответствует примеру из условия)

Позицией в этом дереве Поликарп называет конкретную букву конкретной строки. Позиция записывается как пара целых чисел (v, x), которая обозначает, что позицией является x-ая буква строки sv (1 < v ≤ n, 0 ≤ x < |sv|), где |sv| — длина строки sv. Например, выделенные буквы — это позиции (2, 1) и (3, 1).

Рассмотрим пару позиций (v, x) и (u, y) в дереве Поликарпа, такую, что путь от первой позиции ко второй идет сверху вниз в дереве Поликарпа, нарисованном на плоскости. Будем считать, что пара этих позиций определяет строку z. Строка z состоит из всех букв на пути от (v, x) к (u, y), записанных в порядке прохождения этого пути. Например, на рисунке выделенные позиции определяют строку «bacaba».

У Поликарпа есть строка t, он хочет узнать, сколько существует пар позиций, которые определяют строку t. Обратите внимание, что путь от первой позиции ко второй в паре должен всюду вести вниз. Помогите ему с этой нелегкой древесно-строковой задачей!

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

В первой строке задано целое число n (2 ≤ n ≤ 105) — количество вершин дерева Поликарпа. В следующих n - 1 строках заданы ребра дерева. В i-ой из них записаны число pi + 1 и строка si + 1 (1 ≤ pi + 1 ≤ npi + 1 ≠ (i + 1)). Строка si + 1 — непустая и состоит из строчных букв латинского алфавита. В последней строке записана строка t. Строка t состоит из строчных букв латинского алфавита, ее длина не менее 2.

Гарантируется, что входные данные содержат не более 3·105 букв латинского алфавита.

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

Выведите единственное целое число — искомое количество.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d

Примеры
Входные данные
7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
aba
Выходные данные
6
Входные данные
7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
bacaba
Выходные данные
4
Примечание

В первом тестовом примере строку «aba» определяют пары позиций: (2, 0) и (5, 0); (5, 2) и (6, 1); (5, 2) и (3, 1); (4, 0) и (4, 2); (4, 4) и (4, 6); (3, 3) и (3, 5).

Обратите внимание, что эту строку не определяет пара позиций (7, 1) и (5, 0), потому как путь между ними не всегда идет вниз.