Споживання мізків
Два зомбі грають у гру, метою якої є з'їсти мізки свого суперника. Гра відбувається на дошці з кількома колами, з'єднаними стрілками. На кожній стрілці написана маленька англійська літера. Жодні дві стрілки, що виходять з одного кола, не мають однакової літери. На початку гри гравці обирають спеціальне виграшне слово, розміщують фішку в стартовому колі та починають ходити. У кожному ході зомбі кидає кубик з літерами від 'a' до 'z', які випадають з однаковою ймовірністю. Потім фішка переміщується по стрілці з випавшою літерою, що виходить з поточного кола, і хід переходить до суперника. Якщо стрілки з випавшою літерою немає, гравець кидає кубик знову. Літери, за якими відбувається переміщення, записуються для формування рядка. Коли виграшне слово вперше з'являється як підрядок цього рядка, гра зупиняється, і зомбі, який зробив останній хід, перемагає і з'їдає мозок суперника.
Існує одна важлива деталь. Давня легенда говорить про істоту, що спить глибоко в океані. Той, хто напише магічну фразу, розбудить цю істоту. Пробуджена, вона буде їсти мізки всіх. Небезпека цієї фрази в тому, що для пробудження істоти достатньо написати текст, що містить магічну фразу як підпослідовність. Очевидно, що два зомбі можуть випадково написати щось, що містить магічну фразу, наближаючи Апокаліпсис.
Ви, ймовірно, задаєтеся питанням, скільки ходів знадобиться, поки не буде з'їдений чийсь мозок. Більш конкретно, вас цікавить математичне очікування кількості ходів до цієї події. Напишіть програму, щоб задовольнити вашу цікавість.
Вхідні дані
Перша стрічка містить два цілі числа n і m - кількість кіл на дошці та кількість стрілок відповідно (1 ≤ n ≤ 20). Кожна з наступних m стрічок описує одну стрілку у форматі "u v c" (без лапок). Стрілка йде від u-го до v-го кола і позначена літерою c. Кола пронумеровані від 1 до n, і кожне коло має хоча б одну вихідну стрілку. Стартове коло завжди має номер 1. Далі йдуть два рядки. Перший рядок містить слово, обране зомбі, другий - магічна фраза. І слово, і магічна фраза непорожні і складаються лише з англійських літер нижнього регістру. Слово містить не більше 10 літер, фраза - не більше 50 літер.
Вихідні дані
Виведіть одне число з принаймні двома десятковими знаками - відповідь на задачу. Якщо існує ненульова ймовірність того, що гра ніколи не закінчиться, виведіть "Infinity". Гарантується, що якщо відповідь скінченна, вона не перевищуватиме 10^6.