시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB162503930.469%

## 문제

You are given a set of N integer sequences Z = {Z1, Z2, ··· , ZN}, where |Zi| = K for i = 1, 2, ··· , N.

The N integer sequences in the set were generated by the following generation process:

1. For i-th generation, select a binary integer sequence X ∈ B arbitrary, where B is a set of binary sequences of length K. Let’s denote X = {x1, x2, ··· , xK} where xj ∈ {0, 1} for j = 1, 2, ··· , K.
2. Select a binary integer sequence Y ∈ B arbitrary so that dist(X, Y) ≤ 2. Here dist(X, Y) denotes the hamming distance between X and Y , which is the distance measure between two sequences of equal length is the number of positions at which the corresponding digits are different. For example, dist({1, 0, 1, 1}, {1, 1, 1, 1}) is 1 and dist({1, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 0, 0, 1}) is 2.
3. As the final result, we can generate an integer sequence Zi, by given X and Y. Zi is the i-th generated integer sequence defined by Zi = {x1 + y1, x2 + y2, · · · , xK + yK}.

For example, an integer sequence Zi = {1, 0, 1, 2, 2} can be generated by two binary sequences X = {1, 0, 0, 1, 1} and Y = {0, 0, 1, 1, 1}.

Given N integer sequences generated, write a program to find how many elements in the set B. If there are several possible solutions, find the one with minimum set size.

## 입력

The first line of the input contains two integers K and N (1 ≤ K ≤ 20, 1 ≤ N ≤ 24). A whitespace character separates those two numbers. Each of the following N lines contains elements of Z. The jth number in the i-th line represents Zi,j, the value of the j-th element of Zi. There are no delimiter characters between adjacent numbers in these N lines.

## 출력

Print the minimum number of elements in the set B.

## 예제 입력 1

5 2
10122
20022


## 예제 출력 1

2


## 힌트

In the sample, we can generate each element in the set Z by letting X = {1, 0, 0, 1, 1}, Y = {0, 0, 1, 1, 1} and X = {1, 0, 0, 1, 1}, Y = {1, 0, 0, 1, 1}, respectively. Therefore, Z can be constructed by the set B = {{1, 0, 0, 1, 1} and {0, 0, 1, 1, 1}}.