K. Работа после вуза
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Игорь закончил магистратуру, и, как порядочный студент, решил устроиться на работу по специальности в его любимом городе.

В любимом городе Игоря есть хорошие IT-компании: Accelcomp, Тензор, Akvelon, Fogsoft, Confirmit, Krista и многие другие.

У Игоря есть $$$n$$$ друзей, которые тоже хотят устроиться на работу. Собравшись всей своей дружной компанией, ребята выбрали $$$n+1$$$ IT-компанию из своего родного города.

Игорь и его друзья хотят устроиться в разные компании, чтобы после испытательного срока поделиться впечатлением от работы в IT. Каждый друг Игоря, как и сам Игорь, высказали, хотят ли они работать в определенной компании. Сможете ли вы посчитать сколькими разными способами они смогут устроиться на работу?

Входные данные

В первой строке записано $$$n$$$ $$$(1\leq n \lt 10)$$$ — количество друзей Игоря.

Следующие $$$n+1$$$ строк описывают предпочтения Игоря и его друзей. В строке с номером $$$i$$$ содержится $$$n + 1$$$ число $$$k_{ij}$$$ $$$(1\leq i,\;j \leq n + 1)$$$. Если $$$k_{ij}= 0$$$, то человек с номером $$$i$$$ не хочет работать в компании с номером $$$j$$$, если же $$$k_{ij} = 1$$$, то человек $$$i$$$ хочет работать в компании $$$j$$$.

Выходные данные

В единственной строке выведите количество вариантов трудоустройства студентов с учетом их пожеланий.

Примеры
Входные данные
2
1 1 1
1 1 1
1 1 1
Выходные данные
6
Входные данные
2
1 1 0
0 1 1
0 0 1
Выходные данные
1
Входные данные
2
1 1 0
0 1 0
1 0 0
Выходные данные
0