Maze

Bob is the captain of the USS Spacey McSpaceface, the pride of the Human Empire's space fleet. He is also the last person alive on board.

An unrecognized virus drove the ship's AI, Alpha 5, out of control. Alpha 5 pumped neurotoxin into the crew quarters and killed everyone. Bob was on the bridge at the time, where he grabbed a detoxification kit and a gas mask. Alpha 5 then locked the ship's controls and started the self destruction sequence, so Bob is adrift in space, alone with a rampant AI.

An engineer once told Bob that an override switch sits near the fusion reactor that powers the ship, so Bob starts down toward the engine quarters. The virus has taken over the automatic door system too, and every door now opens and closes on its own.

Bob knows three things about the doors:

• every door carries a single large white letter;
• every room has a display that announces the next letter, so when the display shows an A, every door labeled A opens and every other door slams shut;
• a door stays open for about half a second, just long enough for Bob to dash into the next room.

Bob wants to keep moving, so he uses a door whenever he can. For each announced letter he walks through a door carrying that letter if such a door leads out of the room he is in. He does not know the way to the core, so when several such doors are available he picks one of them with equal probability. Doors between the same pair of rooms count separately: if three doors carrying an A lead from his room to the same neighbor, then three of his choices lead to that neighbor. If no door out of his room carries the announced letter, Bob waits where he is. As soon as Bob enters room $n$ he flips the override switch and stops moving.

Given the sequence of letters until the explosion, compute the probability that Bob reaches the reactor core in time.

The input consists of:

• one line with two integers $n$ ($2 \le n \le 1000$) and $m$ ($1 \le m \le 5000$), where $n$ is the number of rooms in the engine quarters and $m$ is the number of doors between them;
• $m$ lines describing the doors. Each line has two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$) and a letter $l$ from A to Z, describing a door between room $a$ and room $b$ that carries the letter $l$ on both sides. Several doors may join the same pair of rooms, and they may carry the same letter or different letters;
• one line with the order in which the doors open. This line holds at most 200 letters from A to Z.

After the last letter every door slams shut, and the ship explodes if Bob has not reached the switch yet. Bob starts on the bridge, room 1, and the override switch is in room $n$.

Print the probability, as a percentage, that Bob reaches the override switch in time. Round the value to exactly six digits after the decimal point.