#include <iostream>
#include <cmath>
using namespace std;


//given vote counts (totalling n) for 3 (or 4) candidates, find the winner
//returns True if yes, False if no
//Z never steals votes from A, so no ZA** votes
//Z either at front or back, so 1&2 pos enough to uniquely identify non-stolen votes
//booleans true if candidate still in the running, false if already eliminated
char get_winner(int n, int ab, int ac, int ba, int bc, int ca, int cb, int zbc, int zba, int zcb, int zca, bool A=true, bool B=true, bool C=true, bool Z=true)
{
    //tally first-place votes
    int a = ab + ac;
    int b = ba + bc;
    int c = ca + cb;
    int z = zbc + zba + zcb + zca;

    //if someone has more than half the first-place votes, they win
    float half = n/2.0;
    if (A && a > half) return 'A';
    if (B && b > half) return 'B';
    if (C && c > half) return 'C';
    if (Z && z > half) return 'Z';

    //no clear winner, eliminate the loser and reallocate votes
    //reallocate to the next candidate that isn't eliminated
    //in round 2, un-stolen votes will be of the form *Z
    //allocate these to any *-type vote, since all that matter is the first-place tally
    //set reallocated vote quantities to n+1 instead of 0,
    //so real vote counts will always be less (hacky logic)
    //and set boolean flags to false for eliminated candidate
    if (A && a < b && a < c && a < z)    //eliminate A
    {
        //reallocate ab(c) and ac(b)
        //ab(c)
        if (B) bc += ab;
        else if (C) ca += ab;   //any c
        else zbc += ab;         //any z
        //ac(b)
        if (C) cb += ac;
        else if (B) bc += ac;   //any b
        else zbc += ac;         //any z
        ab = n+1;
        ac = n+1;
        A = false;
    }

    else if (B && b <= a && b < c && b < z)   //eliminate B
    {
        //reallocate ba(c) and bc(a)
        //ba(c)
        if (A) ac += ba;
        else if (C) ca += ba;   //any c
        else zbc += ba;         //any z
        //bc(a)
        if (C) ca += bc;
        else if (A) ac += bc;   //any a
        else zbc += bc;         //any z
        ba = n+1;
        bc = n+1;
        B = false;
    }

    else if (C && c <= a && c <= b && c < z)  //eliminate C
    {
        //reallocate ca(b) and cb(a)
        //ca(b)
        if (A) ab += ca;
        else if (B) ba += ca;   //any b
        else zbc += ca;         //any z
        //cb(a)
        if (B) ba += cb;
        else if (A) ab += cb;   //any a
        else zbc += cb;         //any z
        ca = n+1;
        cb = n+1;
        C = false;
    }

    else if (Z && z <= a && z <= b && z <= c) //eliminate Z
    {
        //reallocate zba, zbc, zca, zcb
        //zba(c)
        if (B) ba += zba;
        else if (A) ac += zba;
        else ca += zba;     //any c
        //zbc(a)
        if (B) bc += zbc;
        else if (C) ca += zbc;
        else ab += zbc;     //any a
        //zca(b)
        if (C) ca += zca;
        else if (A) ab += zca;
        else ba += zca;     //any b
        //zcb(a)
        if (C) cb += zcb;
        else if (B) ba += zcb;
        else ac += zcb;     //any a
        zba = n+1;
        zbc = n+1;
        zca = n+1;
        zbc = n+1;
        Z = false;
    }

    //recurse on updated vote counts
    return get_winner(n, ab, ac, ba, bc, ca, cb, zbc, zba, zcb, zca, A, B, C, Z);
}



int main()
{
    int n, k;                   //number of votes, number of candidates
    char first, second, third;  //ranked candidates

    cin >> n >> k;

    //if k=2, very simple, get it over with
    if (k == 2)
    {
        int a = 0;      //count of votes where A is ranked first
        for (int i = 0; i < n; i++)
        {
            cin >> first >> second;
            if (first == 'A') a++;
        }

        //if a >= ceil(n/4), possible to make A win
        if (a >= ceil(n/4.0))
            cout << 1 << endl;
        else
            cout << 0 << endl;

        return 0;
    }

    //everything that follows is for k=3

    //setup vote tracking - vote type counts are sufficient
    //vote types, coded by first two rankings
    int ab = 0, ac = 0, ba = 0, bc = 0, ca = 0, cb = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> first >> second >> third;
        //count vote
        if (first == 'A' && second == 'B') ab++;
        else if (first == 'A' && second == 'C') ac++;
        else if (first == 'B' && second == 'A') ba++;
        else if (first == 'B' && second == 'C') bc++;
        else if (first == 'C' && second == 'A') ca++;
        else if (first == 'C' && second == 'B') cb++;
    }

    //try all possible combos of stealing x B-first votes and y C-first votes
    //only n^2, and n is pretty small
    //when stealing, steal A-last votes before A-middle
    for (int x = 0; x <= ba + bc; x++)
    {
        for (int y = 0; y <= ca + cb; y++)
        {
            //A vote counts unmodified (never stolen)
            //steal from BCA before BAC
            //steal from CBA before CAB
            //Z counts based on what stolen
            //ternary cheatsheet: condition ? true : false
            //argument order: n, ab, ac, ba, bc, ca, cb, zbc, zba, zcb, zca
            if (get_winner(n, ab, ac,
                x < bc ? ba : ba - (x - bc),
                x < bc ? bc - x : 0,
                y < cb ? ca : ca - (y - cb),
                y < cb ? cb - y : 0,
                x <= bc ? x : bc,
                x > bc ? x - bc : 0,
                y <= cb ? y : cb,
                y > cb ? y - cb : 0
                ) == 'A')
            {
                //A wins, print and quit
                cout << 1 << endl;
                return 0;
            }
        }
    }
    //made it here, no solution
    cout << 0 << endl;
}