Given an undirected graph $G$, count the number of $k$-cycles in it.
Input
The first line contains two positive integers $n$ and $k$, representing the number of vertices in the graph and the length of the cycles to be counted.
The next $n$ lines contain the adjacency matrix of the graph, where $A_{ij} = 1$ indicates an edge between $(i, j)$. It is guaranteed that there are no self-loops and the graph is undirected.
Output
Output a single number representing the number of cycles.
Examples
Input 1
6 3 001110 001011 110011 100010 111100 011000
Output 1
4
Input 2
6 4 001110 001011 110011 100010 111100 011000
Output 2
3
Input 3
6 5 001110 001011 110011 100010 111100 011000
Output 3
2
Input 4
6 6 001110 001011 110011 100010 111100 011000
Output 4
1
Input 5
10 3 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Output 5
10
Input 6
10 4 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Output 6
27
Input 7
10 5 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Output 7
66
Input 8
10 6 0100011001 1010101100 0101001101 0010101001 0101011000 1000100101 1111100100 0110011010 0000000101 1011010010
Output 8
123
Input 9
20 4 01111001011011011110 10101010100001000100 11011101010010111110 10101110110010000010 11110010001101111111 00110001000100100100 01011001111011011110 10100110110011011001 01010011000011001110 10110011001110100111 10001010010011111000 00001100010010110001 10110011111100111100 11001011101000010101 00101100011110011100 10101011001111100000 10101011101010100101 11101110110011101010 10111010110000000100 00001001010101001000
Output 9
1267
Subtasks
For $20\%$ of the data, $n \leq 10$.
For another $10\%$ of the data, $k = 3$.
For another $20\%$ of the data, $k = 4$.
For another $30\%$ of the data, $k = 5$.
For $100\%$ of the data, $1 \leq n \leq 300, k \leq 6$.