Є \(N\) міст. Час, необхідний для подорожі з міста \(i\) до міста \(j\), дорівнює \(T_{i, j}\).

Серед тих шляхів, які починаються у місті 1 і проходять всі інші міста рівно один раз з повернненням до міста 1, знайдіть кількість тих, на які витрачено рівно \(К\) одиниць часу.

Формат вхідних даних

Перший рядок містить цілі числа \(N, K\) (\(2 \le N \le 8\), \(1 \le K \le 10^9\))

Наступні  \(N\) рядків містять по \(N\) цілих чисел \(T_{i,j}\) (\(1 \le T_{i,j} (i \neq j) \le 10^8\), \(T_{i,i}=0\), \(T_{i,j}=T_{j,i}\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану кількість шляхів.

Примітка

До прикладу 1:

Є шість шляхів, які починаються з міста 1, відвідують усі інші міста рівно один раз, а потім повертаються до міста 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

Час, необхідний для подорожі цими шляхами, становить відповідно 421, 511, 330, 511, 330 і 421, серед них два рівні 330.

Приклад вхідних даних

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

Приклад вихідних даних

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

Приклад вихідних даних

24