PALACINKE

Anna forgot that several of her friends were coming over for crepes. When she discovered the oversight, she had only \(T\) minutes left to prepare the crepes. She immediately ran out to buy four ingredients: flour (B), eggs (J), milk (M) and jam (P).

In her neighbourhood there are \(N\) intersections numbered \(1,2,\ldots,N\) and \(M\) directed roads connecting them. Each road has a shop that sells at least one of the four ingredients. When Anna traverses a road, she has two choices:

• If she enters the shop on that road to buy something, it takes her 2 minutes to pass the road.
• If she does not enter the shop, it takes 1 minute to pass the road.

(Note that even if she already has all four ingredients, she is allowed to enter a shop.)

Anna must start at intersection 1 and eventually return to intersection 1. She needs to have acquired all four ingredients (\(B, J, M, P\)) within \(T\) minutes (i.e. the total time taken is at most \(T\) minutes). Two shopping routes are considered different if the sequence of intersections visited differs or if the decisions of whether or not to buy on any road differ (the exact purchase is not recorded).

Given the map of the neighbourhood and the time limit, compute the number of different shopping routes modulo \(5557\).

Input Format: See input section below.

Output Format: See output section below.

Translated from [COCI 2010.02 PALACINKE](http://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf)

inputFormat

The first line contains three integers \(T\), \(N\) and \(M\) (in minutes, number of intersections, and number of roads respectively).

Each of the following \(M\) lines contains a description of a road with three items: two integers \(u\) and \(v\) (denoting a directed road from intersection \(u\) to intersection \(v\)) and a string \(S\) consisting only of the characters B, J, M and/or P. The string \(S\) indicates which ingredients are sold in the shop on that road. It is guaranteed that \(S\) is nonempty.

Note: It is allowed that \(u=v\) (a self-loop).

outputFormat

Output a single integer: the number of different shopping routes that allow Anna to collect all four ingredients within \(T\) minutes, modulo \(5557\).

sample

4 2 2
1 2 BJ
2 1 MP

1