단어 세기

탈레스는 먼 섬에서 다음과 같은 게임을 만들었다. 단어 하나를 고른 뒤, 길을 따라 적힌 글자들 속에서 그 단어가 몇 번 나타나는지 세는 것이다. 그는 게임을 더 어렵게 만들기 위해, 현재 위치에서 집으로 돌아가는 배를 탈 수 있는 항구들까지 이어지는 모든 경로를 지도에 그렸다.

길은 트리를 이룬다. 서로 다른 경로는 시작 부분을 공유할 수 있지만, 한 번 갈라진 두 경로는 다시 만나지 않으며, 모든 경로는 서로 다른 항구에서 끝난다. 노드 $0$은 시작점(단어를 고르는 곳)이고, 나머지 노드는 길이 갈라지는 지점이거나 항구(잎)이다. 각 도로 구간(간선)에는 소문자 알파벳으로 이루어진 문자열이 적혀 있다.

시작점에서 항구들로 가는 모든 경로를 따라, 고른 단어가 나타나는 서로 다른 출현의 개수를 세는 것이 당신의 과제이다.

첫째 줄에 노드의 개수를 나타내는 정수 $N$ ($2 \le N \le 15000$)이 주어진다.

다음 $N - 1$개의 줄에는 각각 하나의 도로 정보가 주어진다. 두 정수 $I$와 $J$ ($0 \le I, J \le N - 1$), 그리고 길이가 $L$ ($1 \le L \le 1000$)인 문자열 $S$가 주어지며, 이는 노드 $I$에서 노드 $J$로 향하는 도로에 문자열 $S$가 적혀 있음을 뜻한다. 이때 $I$는 항상 $J$의 부모이다. 노드 $0$으로 들어오는 도로는 없고, 항구에서 시작하는 도로도 없다.

마지막 줄에는 세어야 할 단어가 주어진다. 등장하는 모든 글자는 소문자 알파벳이다.

시작점에서 항구들로 가는 모든 경로를 따라 단어가 나타나는 서로 다른 출현의 개수를 정수 하나로 출력한다.

하나의 출현은 시작 위치와 끝 위치로 식별되며, 끝 위치는 경로를 따라 시작 위치 뒤에 온다. 시작 위치부터 끝 위치까지(양 끝 포함) 연속으로 읽은 글자들이 정확히 그 단어를 이룰 때에만 출현이 존재한다. 두 출현은 시작 위치나 끝 위치가 다르면 서로 다른 것으로 본다.

경로들은 앞부분을 공유하다가 갈라지므로, 공유되는 부분에만 놓인 출현은 한 번만 세고, 갈라지기 전에는 겹치지만 서로 다른 가지에서 끝나는 출현들은 각각 따로 센다.

예제 입력에서 단어 honey는 경로의 다음 부분들을 따라 네 번 나타난다: (0-7-6), (0-7-8), (0-7-2-5), (2-4).