Mice
Турнир за Купата на Декана, 2012
Time Limit: 0.2s, Memory Limit: 64MiB
Както може би знаете, мишките са най-интелигентните същества на Земята. От друга страна, те често биват използвани от хората за най-различни експерименти.

Наскоро мишките изобретиха устройство за клониране в реално време, което се оказа много полезно за намиране на изхода в лабиринт. Когато мишка достигне място с P разклонения, тя просто се клонира P-1 пъти и по една от тях тръгва във всяко от разклоненията (включително това, по което е дошла оригиналната мишка).

Можем да представим лабиринта като множество от N стаи и М коридора между тях. Една от стаите е началната позиция (входа на лабиринта), откъдето тръгват мишките. Друга стая пък е крайната позиция (изходът от лабиринта). Когато мишка достигне изхода, тя мигновено изчезва. За простота началната стая е с номер 1, а крайната – с номер N.

Мишките изминават всеки коридор точно за една секунда. Ако R > 1 мишки достигнат една стая по едно и също време, всички те се клонират по P-1 пъти, като по всеки коридор, свързан със стаята, продължават по R мишки.

Всяка секунда, започвайки от 1, Ели пуска нова мишка във входа на лабиринта, освен в секунди, които се делят на 4 или на 7 (които са щастливи числа за мишките). Определете колко мишки ще са напуснали лабиринта в края на К-тата секунда.
Вход
На първия ред на стандартния вход ще бъде зададени целите числа N, M и K – съответно броя стаи, броя коридори и времето, което Ели провежда експеримента. На всеки от следващите M реда ще бъде зададена по една двойка стаи Ai Bi, свързани с двупосочен коридор. Няма да има повече от един коридор, свързващ две стаи, както и стая, свързана директно със себе си.
Изход
На единствен ред на стандартния изход изведете броя мишки, които ще напуснат лабиринта до K-тата секунда, включително. Тъй като това число може да е наистина огромно, изведете само неговия остатък при деление на 1,000,000,007.
Ограничения
  • 2 ≤ N ≤ 50
  • 1 ≤ M ≤ 1,225
  • 1 ≤ K ≤ 1,000,000
  • 1 ≤ Ai, BiN
Примерен Вход Примерен Изход
6 8 9 1 2 1 3 3 5 2 5 3 4 4 5 6 5 6 4 508
5 9 23 1 2 1 3 1 4 2 3 2 4 3 4 2 5 3 5 4 5 194399846
В първия пример броят мишки в стаите по секунди е:
  1. {1, 0, 0, 0, 0, 0} (излизат 0 мишки)
  2. {1, 1, 1, 0, 0, 0} (излизат 0 мишки)
  3. {3, 1, 1, 1, 2, 0} (излизат 0 мишки)
  4. {2, 5, 6, 3, 3, 0} (излизат 3 мишки) // Ели не добавя мишка
  5. {12, 5, 8, 9, 14, 0} (излизат 6 мишки)
  6. {14, 26, 35, 22, 22, 0} (излизат 23 мишки)
  7. {61, 36, 58, 57, 83, 0} (излизат 44 мишки) // Ели не добавя мишка
  8. {94, 144, 201, 141, 151, 0} (излизат 140 мишки) // Ели не добавя мишка
  9. {346, 245, 386, 352, 486, 0} (излизат 292 мишки)
Мрън!