Word Count
When Thales traveled to a remote island for his summer vacation, he found himself in need of entertainment, as the island was rather uneventful. One day, he noticed words or phrases written along the roads. Although he couldn't understand some of them, he decided to create a game.
In this game, you choose a word and count how many times it appears in the text along a specific segment of the road. After playing this game a few times, Thales devised a more challenging version. He drew a map of the area, marking all possible paths from his current location to the various ports from which he could sail home. He observed that while all paths might start the same, they eventually diverge and never intersect again, each leading to a different port. The rules of this advanced game involve counting the number of distinct occurrences of a chosen word along different paths. Your task is to write a program that accomplishes this.
Input
The first line contains an integer N (2 ≤ N ≤ 15000)—the number of subsequent lines. Each of the next (N-1) lines describes the nodes, which form a tree structure. Node 0 is the starting point, and all other nodes, numbered from 1 to N-1, represent either forks or ports. Each of the next N-1 lines contains two integers representing two nodes I, J (0 ≤ I, J ≤ N-1) and a text S of length L characters (1 ≤ L ≤ 1000), which define the road segment from node I to node J (where I is always a predecessor of J) with text along the road segment. There is no road leading to node 0, and no road exits from a port. The last line of the file contains the word Thales thought of.
Output
The output file should contain a single integer—the number of distinct occurrences of the word along all possible paths. An occurrence is defined by its starting and ending points (the ending point occurs later on the path than the starting point). An occurrence exists when the concatenation of all consecutive characters from the starting to the ending point (inclusive) forms the desired word. An occurrence of the word is considered distinct from another if it has a different starting and/or ending point. All characters are lowercase Latin alphabet letters.
