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≤N≤8\)
• Si \(i ≠ j\), \(1≤T_{i,j}≤10^8\).
• \(T_{i,i} = 0\)
• \(T_{i, j} = T_{j, i}\)
• \(1≤K≤10^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.