Serial Numbers
To check a validity of the software licenses company M* uses serial numbers. Each serial number is a string consisting of exactly n hexadecimal digits. To recog-nize the correct serial number, firm M* uses a state machine. That state machine has k states S_1, S_2, ..., S_k and r transitions between them. Transitions are marked by let-ters, and define the rules of transition from one state to another. The state machine constructed so that all the transitions leading from state Si to other states, necessarily are marked by different letters (that kind of state machine is called deterministic).
Machine starts with the state S_1 and sequentially process n letters of the serial number. Lets assume, that at the moment state machine is in state S_i and process j-th letter of serial number, then:
If there is a transition from the state S_i that is marked with the processed letter and leading to the state S_k, then go to the state S_k and begin processing (j +1)-th letter.
If there is no transition from the state S_i labeled with the j-th letter, then stop processing and assume that the serial number is invalid.
The serial number is valid, if all its letters were successfully processed and the machine returned to the state S_1.
Your task is to determine the number of different serial numbers that the given state machine could recognize as valid.
Input
The first line contains three integers k, n, r, separated by spaces. First line is followed by r rows, each consisting of three numbers S_i, F_i, L_i. The S_i integer is the start state of i-th transition, and the integer F_i – the end state of the transition. The hexadecimal digit L_i is the label of the i-th transition.
2 ≤ k, n ≤ 50; 1 ≤ r ≤ 800. 1 ≤ S_i, F_i ≤ k, where i = 1, … r. ∀ (S_i, F_i, L_i), (S_j, F_j, L_j): S_i = S_j ⇒ L_i ≠ L_j, where i, j = 1, …, r.
Output
The output file should contain a single integer number – the serial numbers' count, which state machine recognize as valid.