Задача №112638. Вернуться за K перелётов

Вася решил немного попутешествовать и выяснил, что между некоторыми городами нет прямых авиарейсов, поэтому придётся лететь с пересадками. Ему стало интересно, можно ли запланировать замкнутый маршрут (который начинается и заканчивается в одном и том же городе), в котором ровно K перелётов. Напишите программу, которая выводит количество таких различных циклических маршрутов. Маршруты, которые проходят через одни и те же города в том же порядке и сводятся только к сдвигу начальной точки цикла (например, 1-2-3-1 и 2-3-1-2), считаются одинаковыми.

Входные данные

В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 50 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему авиационных сообщений. В последней строке вводится число перелётов K .

Выходные данные

Программа должна вывести одно число: количество всех различных замкнутых маршрутов, состоящих из K перелётов.

Примеры
Входные данные
5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
1 0 1 0 1
0 0 0 1 0
3
Выходные данные
2
Сдать: для сдачи задач необходимо войти в систему