Дан неориентированный граф $G$. Посчитайте количество циклов длины $k$ в этом графе.
Входные данные
В первой строке заданы два целых положительных числа $n$ и $k$, обозначающие количество вершин в графе и длину искомых циклов.
Далее следуют $n$ строк, содержащих матрицу смежности графа, где $A_{ij} = 1$ означает наличие ребра между $(i,j)$. Гарантируется, что граф не содержит петель и является неориентированным.
Выходные данные
Выведите одно число — количество циклов.
Примеры
Пример 1–4 (входные данные)
6 [k] 001110 001011 110011 100010 111100 011000
Пример 1–4 (выходные данные)
k=3: 4 k=4: 3 k=5: 2 k=6: 1
Пример 5–8 (входные данные)
10 [k] 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Пример 5–8 (выходные данные)
k=3: 10 k=4: 27 k=5: 66 k=6: 123
Пример 9 (входные данные)
20 4 01111001011011011110 10101010100001000100 11011101010010111110 10101110110010000010 11110010001101111111 00110001000100100100 01011001111011011110 10100110110011011001 01010011000011001110 10110011001110100111 10001010010011111000 00001100010010110001 10110011111100111100 11001011101000010101 00101100011110011100 10101011001111100000 10101011101010100101 11101110110011101010 10111010110000000100 00001001010101001000
Пример 9 (выходные данные)
1267
Примечание
Примечание: первые два примера фактически соответствуют 4 примерам, то есть [k] во входных данных заменяется на $3, 4, 5, 6$ соответственно для получения указанных результатов.
Подсказка
В примерах используется обозначение $[k]$, которое означает, что для данного теста необходимо запустить программу несколько раз, подставляя вместо $[k]$ значения $3, 4, 5, 6$.
Подзадачи
Для $20\%$ данных гарантируется $n\leq 10$.
Для следующих $10\%$ данных гарантируется $k=3$.
Для следующих $20\%$ данных гарантируется $k=4$.
Для следующих $30\%$ данных гарантируется $k=5$.
Для $100\%$ данных гарантируется $1\leq n\leq 300, k\leq 6$.