#include <bits/stdc++.h>
using namespace std;
using namespace std;
long long mask = ((1LL) << 40) - 1;
long long n, m;
long long answer = 0;
vector<long long> nums;
vector<long long> response;
string numToStr(long long x) {
  string s = "";
  while (x) {
    if (x & 1)
      s = s + '1';
    else
      s = s + '0';
    x = x >> 1;
  }
  while (s.length() != n) s = s + '0';
  reverse(s.begin(), s.end());
  return s;
}
void solve(long long x, long long change, long long bitNum) {
  if (change == 0) {
    bool flag = true;
    for (long long i = 0; i < m; i++) {
      long long temp = nums[i] ^ x;
      long long bitSet = n - __builtin_popcountll(temp);
      if (bitSet != response[i]) {
        flag = false;
      }
      if (flag == false) break;
    }
    if (flag == true) {
      answer += 1;
    }
    return;
  }
  if (bitNum == n) return;
  long long toComplement = (x & ((1LL) << bitNum));
  if (toComplement == 0) {
    solve(x, change, bitNum + 1);
    solve((x | ((1LL) << bitNum)), change - 1, bitNum + 1);
  } else {
    solve(x, change, bitNum + 1);
    solve(x & (mask ^ ((1LL) << bitNum)), change - 1, bitNum + 1);
  }
}
long long strToNum(string s) {
  long long answer = 0;
  long long n = s.length();
  long long product = 1;
  for (long long i = n - 1; i >= 0; i--) {
    if (s[i] == '1') answer += product;
    product *= 2;
  }
  return answer;
}
int32_t main() {
  cin >> n >> m;
  long long baseNum;
  long long change;
  for (long long i = 0; i < m; ++i) {
    string s;
    long long x;
    cin >> s;
    cin >> x;
    nums.push_back(strToNum(s));
    response.push_back(x);
    if (i == 0) {
      change = x;
      string s2 = "";
      for (auto c : s) {
        if (c == '0')
          s2 = s2 + '1';
        else
          s2 = s2 + '0';
      }
      baseNum = strToNum(s2);
    }
  }
  solve(baseNum, change, 0);
  cout << answer << endl;
}
