#include <bits/stdc++.h>
using namespace std;
const long long MOD = 12345;
long long GCD(long long a, long long b) {
  while (a > 0) {
    if (a < b) swap(a, b);
    a %= b;
  }
  return b;
}
long long LCM(long long a, long long b) {
  if (a * b == 0) return max(a, b);
  return a * b / GCD(a, b);
}
vector<long long> arr, now;
map<vector<long long>, long long> b;
void Fill(long long n) {
  if (n == arr.size()) {
    long long t = b.size();
    b[now] = t;
    return;
  }
  for (long long i = 0; i < arr[n]; i++) {
    now[n] = i;
    Fill(n + 1);
  }
}
struct M {
  long long arr[130][130];
  M() { memset(arr, 0, sizeof(arr)); }
  M &operator=(const M &a) {
    memcpy(arr, a.arr, sizeof(arr));
    return *this;
  }
  M operator*(const M &a) {
    M ans;
    for (long long i = 0; i < 130; i++)
      for (long long j = 0; j < 130; j++)
        for (long long k = 0; k < 130; k++) {
          ans.arr[i][j] += arr[i][k] * a.arr[k][j];
          ans.arr[i][j] %= MOD;
        }
    return ans;
  }
};
M E(int n) {
  M ans;
  for (long long i = 0; i < n; i++) ans.arr[i][i] = 1;
  return ans;
}
M gr, a;
vector<vector<long long> > dd, d;
vector<bool> f;
int main() {
  long long n;
  long long m;
  cin >> n >> m;
  vector<long long> tmp(26, 0);
  dd.resize(26);
  for (long long i = 0; i < m; i++) {
    char c;
    long long x;
    cin >> c >> x;
    tmp[c - 'A'] = LCM(tmp[c - 'A'], x);
    dd[c - 'A'].push_back(x);
  }
  for (long long i = 0; i < 26; i++)
    if (tmp[i] != 0) {
      arr.push_back(tmp[i]);
      d.push_back(dd[i]);
    }
  now.resize(arr.size());
  Fill(0);
  if (b.size() > 130) throw(0);
  f.assign(b.size(), true);
  for (map<vector<long long>, long long>::iterator it = b.begin();
       it != b.end(); it++) {
    vector<long long> now = it->first;
    for (long long i = 0; i < now.size(); i++) {
      bool ok = false;
      for (long long j = 0; j < d[i].size(); j++)
        if (now[i] % d[i][j] == 0) ok = true;
      if (!ok) f[it->second] = false;
    }
    for (long long i = 0; i < now.size(); i++) {
      vector<long long> tmp = now;
      tmp[i]++;
      tmp[i] %= arr[i];
      if (!b.count(tmp)) throw(0);
      gr.arr[it->second][b[tmp]]++;
      gr.arr[it->second][b[tmp]] %= MOD;
    }
  }
  a = gr;
  gr = E(b.size());
  while (n > 0) {
    if (n % 2 == 1) {
      gr = gr * a;
      n--;
    } else {
      a = a * a;
      n /= 2;
    }
  }
  long long ans = 0;
  for (long long i = 0; i < b.size(); i++)
    if (f[i]) {
      ans += gr.arr[0][i];
      ans %= MOD;
    }
  cout << ans << endl;
  return 0;
}
