팬케이크 재료 사러 가는 길

동혁이는 팬케이크를 만들기 위해 밀가루(B), 달걀(J), 우유(M), 잼(P)을 모두 사야 한다.

동네에는 1번부터 N번까지 번호가 붙은 교차로 N개와 방향 도로 R개가 있다. 동혁이는 처음에 1번 교차로에 있다. 각 도로에는 상점이 하나 있으며, 그 상점은 네 가지 재료 중 하나 이상을 판다.

도로를 지날 때 상점에 들르지 않으면 1분이 걸리고, 상점에 들러 재료를 사며 지나가면 2분이 걸린다. 이미 필요한 재료를 모두 모았더라도 가격을 비교하기 위해 상점에 들를 수 있다.

동혁이가 1번 교차로에서 출발해 네 재료를 모두 모은 뒤 K분 이내에 다시 1번 교차로로 돌아오는 서로 다른 방법의 수를 구하라. 서로 다른 방법은 지나간 도로의 순서와 각 도로에서 상점에 들렀는지 여부의 순서로 구분한다.

답이 매우 커질 수 있으므로 5557로 나눈 나머지를 출력한다.

첫째 줄에 교차로의 수 N과 도로의 수 R이 주어진다. (1 <= N <= 25, 1 <= R <= 500)

다음 R개의 줄에는 도로의 정보가 주어진다. 각 줄에는 서로 다른 정수 u, v와 문자열 s가 공백으로 구분되어 주어진다. 이는 u번 교차로에서 v번 교차로로 가는 방향 도로가 있고, 그 도로의 상점에서 s에 적힌 재료를 판다는 뜻이다.

문자열 s는 길이 1 이상 4 이하의 대문자 문자열이다. 밀가루는 B, 달걀은 J, 우유는 M, 잼은 P로 표시한다. 두 교차로 사이에는 도로가 최대 2개까지 있을 수 있으며, 2개가 있다면 방향은 서로 반대이다.

마지막 줄에는 동혁이가 모든 재료를 구하고 1번 교차로로 돌아와야 하는 시간 제한 K가 주어진다. (1 <= K <= 1,000,000,000)

첫째 줄에 K분 이내에 모든 재료를 구하고 1번 교차로로 돌아오는 서로 다른 방법의 수를 5557로 나눈 나머지를 출력한다.