#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> P;
typedef pair <P,P> PP;

char str[10];
int cnt[30];
map <string,int>::iterator it;

bool solve2(map <string,int> mp,int low){
	memset(cnt,0,sizeof(cnt));
	for(it=mp.begin();it!=mp.end();it++){
		string S=it->first;
		cnt[S[0]-'A']+=it->second;;
	}
	//nothing
	if(cnt[0]>=cnt[25]&&cnt[1]>=cnt[25]){
		if(cnt[0]+mp["ZAB"]>=cnt[1]+mp["ZBA"]){
			return true;
		}
	}
	//use Z
	for(int z=0;z<=cnt[1];z++){
		int l=cnt[1]-z;
		if(l<low) continue;
		map <string,int> now=mp;
		now["BA"]-=z;
		//nxt["ZBA"]+=z;
		int zan=max(l-z+1,0);
		if(zan>now["AB"]) continue;
		now["AB"]-=zan;
		//nxt["ZAB"]+=zan;
		if(now["AB"]<l) continue;
		int a=now["AB"];
		int n=z+zan+now["ZAB"]+now["ZBA"];
		if(a<n) continue;
		return true;
	}
	return false;
}
bool solve(map <string,int> mp){
	memset(cnt,0,sizeof(cnt));
	for(it=mp.begin();it!=mp.end();it++){
		string S=it->first;
		cnt[S[0]-'A']+=it->second;;
	}
	//nothing
	if(cnt[2]<=min(cnt[0],cnt[1])){
		memset(cnt,0,sizeof(cnt));
		for(it=mp.begin();it!=mp.end();it++){
			string S=it->first;
			for(int i=0;i<3;i++){
				if(S[i]=='C') continue;
				cnt[S[i]-'A']++;
				break;
			}
			if(cnt[0]>=cnt[1]) return true;
		}
	}
	//use Z
	for(int z=0;z<=cnt[2];z++){
		int l=cnt[2]-z;
		int cur=z;
		map <string,int> now=mp;
		map <string,int> nxt;
		int zan=z;
		while(zan>0){
			if(now["CBA"]>0){
				int m=min(zan,now["CBA"]);
				zan-=m;
				nxt["ZBA"]+=m;
				now["CBA"]-=m;
			} else{
				int m=min(zan,now["CAB"]);
				zan-=m;
				nxt["ZAB"]+=m;
				now["CAB"]-=m;
			}
		}
		zan=max(l+1-z,0);
		if(cnt[1]<l||cnt[0]<l) continue;
		int b=max(cnt[1]-l,0);
		while(zan>0&&b>0){
			if(now["BCA"]>0){
				int m=min(zan,now["BCA"]);
				m=min(m,b);
				zan-=m;
				b-=m;
				nxt["ZBA"]+=m;
				now["BCA"]-=m;
			} else{
				int m=min(zan,now["BAC"]);
				m=min(m,b);
				zan-=m;
				b-=m;
				nxt["ZBA"]+=m;
				now["BAC"]-=m;
			}
		}
		int a=max(cnt[0]-l,0);
		while(zan>0&&a>0){
			if(now["ACB"]>0){
				int m=min(zan,now["ACB"]);
				m=min(m,a);
				zan-=m;
				a-=m;
				nxt["ZAB"]+=m;
				now["ACB"]-=m;
			} else{
				int m=min(zan,now["ABC"]);
				m=min(m,a);
				zan-=m;
				a-=m;
				nxt["ZAB"]+=m;
				now["ABC"]-=m;
			}
		}
		for(it=now.begin();it!=now.end();it++){
			string T="";
			string S=it->first;
			for(int i=0;i<3;i++){
				if(S[i]=='C') continue;
				T+=S[i];
			}
			nxt[T]+=it->second;
		}
		if(solve2(nxt,l)) return true;
	}
	return false;
}
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	map <string,int> mp;
	map <string,int>::iterator it;
	for(int i=0;i<n;i++){
		string S="";
		for(int j=0;j<k;j++){
			scanf("%s",&str);
			S+=str[0];
		}
		if(k==2){
			S+="C";
		}
		mp[S]++;
	}
	for(int t=0;t<2;t++){
		if(solve(mp)){
			puts("1");
			return 0;
		}
		map <string,int> nxt;
		for(it=mp.begin();it!=mp.end();it++){
			string S=it->first;
			int c=it->second;
			for(int i=0;i<3;i++){
				if(S[i]=='B') S[i]='C';
				else S[i]='B';
			}
			nxt[S]=c;
		}
		mp=nxt;
	}
	puts("0");
}