Серійні номери#2558
Щоб перевірити дійсність програмних ліцензій, компанія M* використовує серійні номери. Кожен серійний номер — це рядок з рівно шістнадцяткових цифр. Для розпізнавання правильних серійних номерів компанія M* використовує скінченний автомат. Автомат має станів S_1, S_2, \ldots, S_k і переходів між ними. Переходи марковані цифрами чи літерами та визначають правила переходу з одного стану в інший. Автомат побудовано так, що всі переходи з будь-якого стану S_i до інших станів унікально марковані різними символами (такий автомат називається детермінованим).
Автомат починає роботу зі стану S_1 і послідовно опрацьовує цифр серійного номера. Нехай на певному кроці автомат перебуває у стані S_i й опрацьовує -у цифру серійного номера. Тоді:
Якщо існує перехід зі стану S_i, маркований поточною цифрою і веде у стан S_k, перейти у стан S_k і опрацювати (j+1)-у цифру.
Якщо переходу зі стану S_i, маркованого -ю цифрою, не існує, зупинити обробку й вважати серійний номер недійсним.
Серійний номер вважається дійсним, якщо всі його цифри успішно опрацьовані, і наприкінці автомат повертається у стан S_1.
Ваше завдання — визначити, скільки різних серійних номерів цей автомат може розпізнати як дійсні.
У першому рядку записано три цілі числа , , , розділених пробілами. Далі йдуть рядків, у кожному з яких записано три значення S_i, F_i, L_i. Число S_i — це початковий стан -го переходу; F_i — кінцевий стан; шістнадцяткова цифра L_i — мітка переходу.
2 \le k, n \le 50; 1 \le r \le 800. 1 \le S_i, F_i \le k, i = 1, \ldots, r. Для всіх (S_i, F_i, L_i), (S_j, F_j, L_j): якщо S_i = S_j, то L_i \ne L_j, для i, j = 1, \ldots, r.
У вихідний файл виведіть одне ціле число — кількість серійних номерів, які автомат розпізнає як дійсні.
Приклад 1