#!/usr/bin/env python3
from collections import defaultdict


def solve2(n):
    """
    Solve the 2 player game.

    Say we have x copies of A*, y copies of ZBA, and z copies of BAZ
    We need x >= z and x + z >= y
    Might as well set z = x.
    Then we have 2x >= y, x + y = n
    x has to be at least 1/4
    """
    x = 0
    for _ in range(n):
        x += input() == "A B"

    return 4 * x >= n


def can_win(ballots):
    alive = {"A", "B", "C", "Z"}
    for _ in range(4):
        votes = {cand: 0 for cand in alive}
        total = 0
        for ballot, freq in ballots.items():
            winner = [cand for cand in ballot.split() if cand in alive][0]
            votes[winner] += freq
            total += freq

        # A has won
        if 2 * votes["A"] > total:
            return True

        # Someone else has won
        if any(2 * freq > total for freq in votes.values()):
            return False

        # Eliminate the loser
        min_freq = min(votes.values())
        loser = max(cand for cand in alive if votes[cand] == min_freq)
        if loser == "A":
            return False

        alive.remove(loser)

    return False


def take(ballots, want, taken=0):
    want -= taken
    if want <= 0:
        return 0, ballots

    take = min(ballots, want)
    return take, ballots - take


def solve3(n):
    """
    There are 6 starting ballots:
    ABC
    ACB
    BAC
    BCA
    CAB
    CBA

    Z doesn't matter for first two.
    For others, Z should either go to the beginning or the end. This gives the
    following "useful" ballots:

    A*
    ZBAC
    BACZ
    ZBCA
    BCAZ
    ZCAB
    CABZ
    ZCBA
    CBAZ

    Iterating over all splits is O(n^4). To reduce complexity to O(n^2), note that you prefer to "spoil" BCA before you spoil BAC. Same for CBA over CAB.
    """
    freq = defaultdict(int)
    for _ in range(n):
        freq[input()] += 1

    b = freq["B A C"] + freq["B C A"]
    c = freq["C A B"] + freq["C B A"]

    for x in range(b + 1):
        votes = {}
        votes["A B C Z"] = freq["A B C"]
        votes["A C B Z"] = freq["A C B"]

        votes["Z B C A"], votes["B C A Z"] = take(freq["B C A"], x)
        votes["Z B A C"], votes["B A C Z"] = take(freq["B A C"], x, freq["B C A"])
        for y in range(c + 1):
            votes["Z C B A"], votes["C B A Z"] = take(freq["C B A"], y)
            votes["Z C A B"], votes["C A B Z"] = take(freq["C A B"], y, freq["C B A"])

            assert sum(freq.values()) == sum(votes.values())
            if can_win(votes):
                return True

    return False


def main():
    n, k = map(int, input().split())
    can_spoil = False
    if k == 2:
        can_spoil = solve2(n)
    else:
        can_spoil = solve3(n)

    print(1 if can_spoil else 0)


if __name__ == "__main__":
    main()