Buying Pancake Ingredients

Donghyuk wants to make pancakes, so he must buy all four ingredients: flour (B), eggs (J), milk (M), and jam (P).

His neighborhood has N intersections numbered from 1 to N and R directed roads. Donghyuk starts at intersection 1. Each road has exactly one shop, and the shop sells at least one of the four ingredients.

When he travels along a road, passing without visiting the shop takes 1 minute. Visiting the shop and buying ingredients while passing takes 2 minutes. Even after collecting all required ingredients, he may still visit shops to compare prices.

Count the number of different ways for Donghyuk to start at intersection 1, collect all four ingredients, and return to intersection 1 within K minutes. Two ways are different if the time-ordered sequence of roads or shop-visit choices differs.

Because the answer can be very large, output it modulo 5557.

The first line contains the number of intersections N and the number of roads R. (1 <= N <= 25, 1 <= R <= 500)

Each of the next R lines contains two distinct integers u and v and a string s. This means there is a directed road from intersection u to intersection v, and the shop on that road sells the ingredients listed in s.

The string s has length from 1 to 4 and consists of uppercase letters. Flour is B, eggs are J, milk is M, and jam is P. Between the same two intersections there can be at most two roads; if there are two, their directions are opposite.

The last line contains the time limit K by which Donghyuk must collect all ingredients and return to intersection 1. (1 <= K <= 1,000,000,000)

Print one integer: the number of different ways to collect all ingredients and return to intersection 1 within K minutes, modulo 5557.