시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 160 44 37 30.833%

문제

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.

예제 입력

5 2
10122
20022

예제 출력

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}}.