Підрахунок слів
Коли Фалес виїхав на віддалений острів, для того щоб провести літню відпустку, йому довелось пошукати, чим би зайнятись, так як на острові було досить сумно. Одного разу Фалес помітив, що вздовж доріг написані слова або фрази. Він не міг зрозуміти деякі з них, але це не зупинило його від придумування гри.
Для того щоб зіграти у цю гру, потрібно придумати слово і порахувати, як багато разів воно зустрічається у тексті вздовж певного сегменту дороги. Після того, як Фалес зіграв у цю гру декілька разів, він придумав простий спосіб підрахунку слів, і вирішив спробувати себу у більш складній грі. Фалес нарисовав карту місцевості і відмітив усі можливі шляхи від його поточного положення до усіх портів, звідки він міг би поплистт додому. Він помітив, що хоча усі шляхи можуть починатись однаково, вони усі в результаті розходяться і більше ніколи не перетинаються – усі вони приводять до різних портів. Правила більш складної гри вимагали порахувати кількість різних появ вибраного слова вздовж різних шляхів. Ваша програма повинна зробити саме це.
Вхідні дані
Перший рядок містить ціле число N (2 ≤ N ≤ 15000) – кількість наступних рядків. Кожен з наступних (N-1)-го рядка файла містить дані про вузли. Усі вузли формують деревовидну структуру. Зокрема, вузол 0 визначає початкову точку, а усі інші вузли, пронумеровані від 1 до N-1, являють або розвилки або порты. Таким чином, кожен з наступних N-1 рядків містить два цілих числа які подають два вузли I, J (0 ≤ I, J ≤ N-1) та текст S довжиною L символів (1 ≤ L ≤ 1000), які задають сегмент дороги від вузла I до вузла J (де I завжди попередник J) з текстом вздовж сегмента дороги. Очевидно, що немає дороги, яка веде до вузла 0, і жодна дорога не виходить з порту. Останній рядок файлу містить задумане Фалесом слово.
Вихідні дані
Вихідний файл повинен містити єдине ціле число – кількість різних появ слова вздовж усіх можливих шляхів. Поява ідентифікується початковою та кінцевою точками (кінцева точка зустрічається на шляху пізніше посаткової). Поява існує, коли конкатенація усіх послідовних символів від початкової до кінцевої точки (включно) формує шукане слово. Поява слова вважаєься відмінною від іншої появи, коли у неї інша кінцева і/або початкова точка. Усі символы – малі символи латинського алфавіту.
