Hay ~N~ ciudades. El tiempo que se tarda en viajar de la ciudad ~i~ a la ciudad ~j~ es ~T_{i, j}~.

Entre esos caminos que comienzan en la Ciudad ~1~, visite todas las demás ciudades exactamente una vez, y luego regrese a la Ciudad ~1~, ¿cuántos caminos toman el tiempo total de exactamente ~K~ para viajar?

Restricciones

• \(2\leN\le8\)
• Si \(i ≠ j\), \(1\leT_{i,j}\le10^8\).
• ~T_{i,i} = 0~
• ~T_{i, j} = T_{j, i}~
• \(1\leK\le10^9\)
• Todos los valores de la entrada son números enteros.

Entrada:

La primera línea de la entrada contiene ~N~ y ~K~. Siguen ~N~ líneas cada una con ~N~ enteros donde el elemento en la i-ésima fila y la columna ~j~ es ~T_{i,j}~.

Salida

Imprime la respuesta como un número entero.

Entrada de ejemplo 1:

4 330
0 1 10100
1 0 20 200
10 20 0 300
100 200 300 0

Salida de ejemplo: 1

2

Hay seis caminos que comienzan en la ciudad ~1~, visita todas las demás ciudades exactamente una vez y luego vuelve a la Ciudad ~1~:

1 → 2 → 3 → 4 → 1 1 → 2 → 4 → 3 → 1 1 → 3 → 2 → 4 → 1 1 → 3 → 4 → 2 → 1 1 → 4 → 2 → 3 → 1 1 → 4 → 3 → 2 → 1

El tiempo que se tarda en recorrer estos caminos es de ~421~, ~511~, ~330~, ~511~, ~330~ y ~421~, respectivamente, entre los cuales dos son exactamente ~330~.

Entrada de ejemplo 2:

5 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Salida de ejemplo 2:

24

En cualquier orden en que visitemos las ciudades, tomará el tiempo total de ~5~ viajar.