이진 수열은 몇 개인가

길이가 $K$인 이진 수열을 모은 집합 $B$가 있다. $B$의 각 원소는 각 항이 $0$ 또는 $1$인 길이 $K$짜리 수열이다.

정수 수열 $Z_i$는 다음 과정으로 만든다.

1. $B$에서 수열 $X = (x_1, x_2, \dots, x_K)$를 하나 고른다.
2. $B$에서 $\mathrm{dist}(X, Y) \le 2$를 만족하는 수열 $Y = (y_1, y_2, \dots, y_K)$를 하나 고른다. 여기서 $\mathrm{dist}(X, Y)$는 두 수열의 해밍 거리, 즉 같은 자리의 값이 서로 다른 자리의 개수다. 예를 들어 $\mathrm{dist}((1,0,1,1), (1,1,1,1)) = 1$이고 $\mathrm{dist}((1,0,1,1,1,0,1), (1,0,0,1,0,0,1)) = 2$이다. $X$와 $Y$로 같은 원소를 고를 수 있다.
3. $Z_i = (x_1 + y_1, x_2 + y_2, \dots, x_K + y_K)$로 둔다.

예를 들어 $Z_i = (1,0,1,2,2)$는 $X = (1,0,0,1,1)$과 $Y = (0,0,1,1,1)$로 만들 수 있다.

이 과정으로 만든 정수 수열 $N$개 $Z_1, Z_2, \dots, Z_N$이 주어진다. 이 $N$개를 모두 만들 수 있는 집합 $B$ 중에서 원소 개수가 가장 적은 것을 찾아, 그 원소 개수를 출력하는 프로그램을 작성하시오.

첫째 줄에 $K$와 $N$이 공백 하나를 사이에 두고 주어진다. ($1 \le K \le 20$, $1 \le N \le 24$)

다음 $N$개 줄에 수열 $Z_i$가 한 줄에 하나씩 주어진다. $i$번째 줄의 $j$번째 문자가 $Z_{i,j}$의 값이고, 문자 사이에 구분자는 없다. 각 값은 $0$, $1$, $2$ 중 하나이며 한 줄에 $1$은 많아야 두 개 나온다. 즉 주어지는 $Z_i$는 모두 위 과정으로 만들 수 있는 수열이다.

첫째 줄에 집합 $B$의 최소 원소 개수를 출력한다.