Задача №77. Путевые строки
Рассмотрим ориентированный граф G, имеющий n вершин, пронумерованных натуральными числами от 1 до n. В графе G возможно наличие нескольких дуг между одной и той же парой вершин, а также дуг, ведущих из вершины в нее саму. Каждая дуга графа помечена некоторой буквой латинского алфавита. Каждому пути в графе G можно поставить в соответствии строку, состоящую из букв, написанных на последовательно проходимых в соответствии с этим путем дугах. Эта строка называется путевой меткой пути. Назовем строку
Ваша задача посчитать остаток от деления на 1 000 000 количества путевых строк графа G, состоящих ровно из L символов.
В первой строке входных данных записаны целые числа n, m, L (1 ≤ n ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 100), равные количеству вершин и ребер графа G, а также длине путевых строк, которые нужно искать. Следующие m строк задают дуги графа G. Каждая из этих строк содержит два натуральных числа a, b (1 ≤ a, b ≤ n) и маленькую латинскую букву c, что означает наличие дуги из вершины a в вершину b, помеченной символом c. Элементы каждой строки отделены друг от друга пробелами.
Единственная строка выходных данных должна содержать одно число, равное остатку от деления количества путевых строк длины L в графе G на 1 000 000.
4 4 100 1 2 a 2 3 b 3 4 a 4 1 b
2