Серійні номери
Щоб перевірити дійсність ліцензій на програмне забезпечення, компанія M* використовує серійні номери. Кожен серійний номер — це рядок, що складається з точно n шістнадцяткових цифр. Для розпізнавання правильного серійного номера, фірма M* використовує автомат. Цей автомат має k станів S_1, S_2, ..., S_k та r переходів між ними. Переходи позначені літерами і визначають правила переходу з одного стану в інший. Автомат побудований так, що всі переходи, які ведуть зі стану Si до інших станів, обов'язково позначені різними літерами (такий автомат називається детермінованим).
Машина починає з стану S_1 і послідовно обробляє n літер серійного номера. Припустимо, що в даний момент автомат знаходиться в стані S_i і обробляє j-ту літеру серійного номера, тоді:
Якщо існує перехід зі стану S_i, який позначений оброблюваною літерою і веде до стану S_k, то перейти до стану S_k і почати обробку (j +1)-ї літери.
Якщо немає переходу зі стану S_i, позначеного j-тою літерою, то зупинити обробку і вважати, що серійний номер недійсний.
Серійний номер є дійсним, якщо всі його літери були успішно оброблені і машина повернулася до стану S_1.
Ваше завдання — визначити кількість різних серійних номерів, які даний автомат може розпізнати як дійсні.
Вхідні дані
У першому рядку містяться три цілі числа k, n, r, розділені пробілами. Перший рядок слідує за r рядками, кожен з яких складається з трьох чисел S_i, F_i, L_i. Ціле число S_i є початковим станом i-го переходу, а ціле число F_i — кінцевим станом переходу. Шістнадцяткова цифра L_i є міткою i-го переходу.
2 ≤ k, n ≤ 50; 1 ≤ r ≤ 800. 1 ≤ S_i, F_i ≤ k, де i = 1, … r. ∀ (S_i, F_i, L_i), (S_j, F_j, L_j): S_i = S_j ⇒ L_i ≠ L_j, де i, j = 1, …, r.
Вихідні дані
Вихідний файл повинен містити одне ціле число — кількість серійних номерів, які автомат розпізнає як дійсні.