To check a validity of the software licenses company M* uses serial numbers. Each serial number is a string consisting of exactly \textbf{n} hexadecimal digits. To recog-nize the correct serial number, firm M* uses a state machine. That state machine has \textbf{k} states \textbf{S_1}, \textbf{S_2}, ..., \textbf{S_k} and \textbf{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 \textbf{S_1} and sequentially process n letters of the serial number. Lets assume, that at the moment state machine is in state \textbf{S_i} and process \textbf{j}-th letter of serial number, then: \begin{enumerate} \item If there is a transition from the state \textbf{S_i} that is marked with the processed letter and leading to the state \textbf{S_k}, then go to the state \textbf{S_k} and begin processing \textbf{(j +1)}-th letter. \item If there is no transition from the state \textbf{S_i} labeled with the \textbf{j}-th letter, then stop processing and assume that the serial number is invalid. \end{enumerate} The serial number is valid, if all its letters were successfully processed and the machine returned to the state \textbf{S_1}. Your task is to determine the number of different serial numbers that the given state machine could recognize as valid. \InputFile The first line contains three integers \textbf{k}, \textbf{n}, \textbf{r}, separated by spaces. First line is followed by \textbf{r} rows, each consisting of three numbers \textbf{S_i}, \textbf{F_i}, \textbf{L_i}. The \textbf{S_i} integer is the start state of \textbf{i}-th transition, and the integer \textbf{F_i} -- the end state of the transition. The hexadecimal digit \textbf{L_i} is the label of the \textbf{i}-th transition. \textbf{2} ≤ \textbf{k}, \textbf{n} ≤ \textbf{50}; \textbf{1} ≤ \textbf{r} ≤ \textbf{800}. \textbf{1} ≤ \textbf{S_i}, \textbf{F_i} ≤ \textbf{k}, where \textbf{i} = \textbf{1}, … \textbf{r}. ∀ (\textbf{S_i}, \textbf{F_i}, \textbf{L_i}), (\textbf{S_j}, \textbf{F_j}, \textbf{L_j}): \textbf{S_i} = \textbf{S_j} ⇒ \textbf{L_i} ≠ \textbf{L_j}, where \textbf{i}, \textbf{j} = \textbf{1}, …, \textbf{r}. \OutputFile The output file should contain a single integer number -- the serial numbers' count, which state machine recognize as valid.