미로

Bob은 인류 제국 우주 함대의 자랑인 USS Spacey McSpaceface의 함장이다. 동시에 이 배에서 살아남은 마지막 사람이다.

정체를 알 수 없는 바이러스에 감염된 함선 AI Alpha 5가 폭주해 승무원 구역에 신경독을 흘려보내 모두를 죽였다. 그때 Bob은 함교에 있었고, 해독 키트와 방독면을 손에 넣었다. 이어서 Alpha 5는 함선 조작 계통을 잠그고 자폭 절차를 시작했다. Bob은 폭주한 AI와 함께 우주에 홀로 떠 있다.

예전에 어느 기술자가 함선에 동력을 공급하는 핵융합로 근처에 강제 정지 스위치가 있다고 알려 준 적이 있다. 그래서 Bob은 기관 구역으로 내려가기 시작한다. 바이러스는 자동문 계통까지 장악했고, 이제 모든 문이 제멋대로 열리고 닫힌다.

Bob이 문에 관해 아는 사실은 세 가지다.

• 모든 문에는 흰색 대문자 하나가 크게 적혀 있다.
• 방마다 다음에 열릴 글자를 알려 주는 큰 표시판이 있다. 표시판에 A가 뜨면 A가 적힌 문이 모두 열리고 나머지 문은 모두 닫힌다.
• 문이 열려 있는 시간은 약 0.5초로, Bob이 옆방으로 뛰어 들어가기에 딱 충분하다.

Bob은 계속 움직이려 하므로 지날 수 있으면 반드시 문을 지난다. 표시판에 글자가 뜰 때마다, 지금 있는 방에서 그 글자가 적힌 문이 하나라도 밖으로 이어지면 그 문으로 나간다. 노심으로 가는 길을 모르기 때문에 그런 문이 여러 개면 그중 하나를 같은 확률로 고른다. 같은 두 방을 잇는 문은 각각 따로 센다. 지금 있는 방에서 같은 이웃 방으로 A가 적힌 문이 세 개 이어지면, 그 이웃 방으로 가는 선택이 세 가지다. 지금 있는 방에서 그 글자가 적힌 문이 하나도 밖으로 이어지지 않으면 Bob은 그 자리에서 기다린다. Bob이 $n$번 방에 들어서는 순간 강제 정지 스위치를 내리고 더 움직이지 않는다.

폭발 전까지 표시판에 뜨는 글자 순서가 주어진다. Bob이 제때 반응로 노심에 도달할 확률을 구하라.

입력은 다음과 같이 주어진다.

• 첫째 줄에 정수 $n$ ($2 \le n \le 1000$)과 $m$ ($1 \le m \le 5000$)이 주어진다. $n$은 기관 구역의 방 개수, $m$은 방 사이 문의 개수다.
• 다음 $m$개 줄에 문 정보가 주어진다. 각 줄에는 정수 $a$와 $b$ ($1 \le a, b \le n$, $a \ne b$), 그리고 A부터 Z까지의 글자 $l$이 주어진다. 이는 $a$번 방과 $b$번 방을 잇는 문이고, 양쪽 면에 글자 $l$이 적혀 있다. 같은 방 쌍을 잇는 문이 여러 개일 수 있으며, 글자는 같을 수도 있고 다를 수도 있다.
• 마지막 줄에 문이 열리는 순서가 주어진다. 이 줄에는 A부터 Z까지의 글자가 200개 이하로 주어진다.

마지막 글자가 지나면 모든 문이 닫히고, 그때까지 Bob이 스위치에 도달하지 못했으면 함선은 폭발한다. Bob은 함교인 1번 방에서 출발하고, 강제 정지 스위치는 $n$번 방에 있다.

Bob이 제때 강제 정지 스위치에 도달할 확률을 백분율로 출력한다. 소수점 아래 여섯째 자리까지 반올림해 출력한다.