Eating Brains
Two zombies are playing a game. The goal of the game is, well, to eat brains. Your opponent's ones, of course. It is played by moving a brain-shaped token on a board. Board has several circles with arrows between them. Each arrow has a small English letter on it. There are no two outgoing arrows from one circle having the same letter. When the game begins, players select special winning word, then place the token at starting circle and start making turns. Each turn zombie rolls a die with letters 'a'. . . 'z' on it fairly. After that she moves the token along the arrow outgoing from the current circle that has selected letter and passes turn to her opponent. If there is no arrow with such letter, she rolls a die once again and so on. Letters of traversed arrows are written down to form a string. When the winning word appears as a substring of this string for the first time, the game stops and zombie who made the last turn wins and eats brain of her opponent.
There is also one thing you should be aware of. Ancient legend says there is a creature sleeping deep in the ocean. Whoever writing magical phrase awakens this creature. Once awakened, it will eat everybody's brains. The real danger of this phrase is that to awake evil creature it is sufficient to write some other text containing magical phrase as subsequence of letters. Obviously, two poor zombies playing the game can eventually write something that contains magical phrase, thus inducing Apocalypse on everyone including themselves.
After reading all this, you most likely wonder, how many turns it will take until somebody's brain will be eaten. More specifically, you are interested in statistical expectation of number of turns until that event. Write a program to satisfy your curiosity.
Input
The first line contains two integers n and m - the number of circles on the game board and the number of arrows respectively (1 ≤ n ≤ 20). Each of the next m lines has description of one arrow in the form "u v c" (without quotes). The edge goes from u-th to v-th circle and has c letter on it. Circles are numbered from 1 to n, each circle has at least one outgoing arrow. Starting circle always has number 1. Then two lines follow. First of them contain a word selected by zombies, second - a secret magical phrase. Both selected word and magical phrase are non-empty and consist only from lowercase English letters. Word has at most 10 letters, phrase - 50 letters in length.
Output
Output must contain one number with at least two digits after decimal point - the answer for this problem. If there is non-zero probability that the game will never end, output "Infinity" instead. It is guaranteed that if the answer is finite, it will not exceed 10^6.