Word Counting

On a distant island, Thales invented a game: he would pick a word and count how many times it appeared in the text written along the roads. To make it harder, he drew a map of every path leading from his current position to the ports from which he could sail home.

The roads form a tree. Different paths may share a common beginning, but once two paths separate they never meet again, and every path ends at a different port. Node $0$ is the origin (where the word is chosen); the remaining nodes are road splits or ports (the leaves). Each road segment is labeled with a text made of lowercase English letters.

Your task is to count all distinct appearances of a chosen word along the paths from the origin to the ports.

The first line contains an integer $N$ ($2 \le N \le 15000$), the number of nodes.

Each of the next $N - 1$ lines describes one road: two integers $I$ and $J$ ($0 \le I, J \le N - 1$) followed by a text $S$ of length $L$ ($1 \le L \le 1000$). This is a road from node $I$ to node $J$ labeled with $S$, where $I$ is the parent of $J$. There is no road into node $0$, and no road starts from a port.

The last line contains the word to count. Every letter that appears is a lowercase English letter.

Print a single integer: the number of distinct appearances of the word along all paths from the origin to the ports.

An appearance is identified by its start position and its end position, where the end position follows the start position along a path. An appearance exists exactly when the letters read consecutively from the start position to the end position (inclusive) spell the word. Two appearances are different if they differ in start position or in end position.

Because paths share a common beginning but branch apart, an appearance that lies entirely on a shared part is counted once, whereas appearances that coincide before a branch but end on different branches are counted separately.

In the example input, the word honey appears four times, along these parts of the paths: (0-7-6), (0-7-8), (0-7-2-5), and (2-4).