acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem D

弁当作り

太郎君は,近頃弁当作りにはまっている. 太郎君は今日新しい弁当レシピ本を手に入れたので,そこに書いてあるレシピをできるだけ多く試してみたいと思っている.

どのレシピに必要な材料も十分に手元にあるのだが,みんな 2 つ入りの真空パックになっている. 1 つだけ使って 1 つ残したら,残った方はすぐ腐ってしまう. かといって同じレシピの弁当を 2 つ作っても面白くない. だから彼は同じ弁当を複数作らず,しかも半端な材料が残らないようなレシピの組み合わせを選ぶことにした.

レシピ本には,同じ材料を使っても違うレシピの弁当も載っているかもしれないことに注意せよ.

この方針に従うと,今日太郎君は最大で何種類のレシピを試せるのだろうか.

Input

入力は 50 個以下のデータセットからなる. 各データセットは次の形式で表される.

n m
b1,1...b1,m
...
bn,1...bn,m

1 行目には,レシピ本に書いてあるレシピの数 n と材料の種類数 m が与えられる. nm は整数であり,1 ≤ n ≤ 500,1 ≤ m ≤ 500,1 ≤ n × m ≤ 500 が成り立つ. 続く n 行には,0 または 1 からなる長さ m の文字列で各レシピの情報が与えられる. bi,ji 番目のレシピに j 番目の材料が必要かどうかを表し,0 の場合は必要ないこと,1 の場合は必要であることを意味する. 各行は少なくとも 1 つ以上の 1 を含む.

入力の終わりは,2 つのゼロからなる行で表される.

Output

各データセットについて,太郎君が試すことのできるレシピの種類の最大数を 1 行に出力せよ.

Sample Input

4 3
110
101
011
110
7 1
1
1
1
1
1
1
1
4 5
10000
01000
00100
00010
6 6
111111
011000
100000
000010
100001
100100
0 0

Output for the Sample Input

3
6
0
6
(End of Problem D) A B C D E F G H