using System;
using System.Numerics;
using System.Globalization;

class P4DansingBits
{
    static void Main()
    {
        int k = int.Parse(Console.ReadLine());
        int n = int.Parse(Console.ReadLine());
        int[] arr = new int[n];
        string binary = null;
        for (int i = 0; i < n; i++)
        {
            arr[i] = int.Parse(Console.ReadLine());
            binary += Convert.ToString(arr[i], 2);
        }
        int strLength = binary.Length;
        BigInteger bigNum = 0;
        foreach (char c in binary)
        {
            bigNum <<= 1;
            bigNum += Convert.ToInt32(c.ToString());
        }
        int danceingNumbersCount = 0;
        int bit = 0;
        while (bit < strLength)
        {
            int localCount = 1;
            while (bit < strLength)
            {
                if (((bigNum >> bit) & 1) == ((bigNum >> (bit + 1)) & 1))
                {
                    localCount++;
                }
                else
                {
                    bit++;
                    break;
                }
                bit++;
            }
            if (localCount == k)
            {
                danceingNumbersCount++;
            }
        }
        Console.WriteLine(danceingNumbersCount);
    }
}