#include <bits/stdc++.h>
using namespace std;
inline void pisz(int n) { printf("%d\n", n); }
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream &operator<<(ostream &s, vector<T> t) {
  for (int(i) = 0; (i) < (((int)(t.size()))); ++(i)) s << t[i] << " ";
  return s;
}
const int MOD = 12345;
int ROZM;
void wypisz(const vector<vector<int> > &m) {
  for (int(i) = 0; (i) < (ROZM); ++(i)) {
    for (int(j) = 0; (j) < (ROZM); ++(j)) cout << m[i][j] << " ";
    cout << endl;
  }
}
vector<vector<int> > id() {
  vector<vector<int> > w(ROZM);
  for (int(i) = 0; (i) < (ROZM); ++(i)) {
    w[i].resize(ROZM, 0);
    w[i][i] = 1;
  }
  return w;
}
vector<vector<int> > zero() {
  vector<vector<int> > w(ROZM);
  for (int(i) = 0; (i) < (ROZM); ++(i)) w[i].resize(ROZM, 0);
  return w;
}
vector<vector<int> > mult(const vector<vector<int> > &m1,
                          const vector<vector<int> > &m2) {
  vector<vector<int> > w = zero();
  for (int(i) = 0; (i) < (ROZM); ++(i))
    for (int(j) = 0; (j) < (ROZM); ++(j))
      for (int(k) = 0; (k) < (ROZM); ++(k)) {
        w[i][j] += m1[i][k] * m2[k][j];
        w[i][j] %= MOD;
      }
  return w;
}
vector<vector<int> > potega(const vector<vector<int> > &m, long long k) {
  if (k == 0) return id();
  vector<vector<int> > x = potega(m, k / 2);
  x = mult(x, x);
  if (k & 1)
    return mult(m, x);
  else
    return x;
}
set<int> mults[300], goodrests[300];
int prod[300], pprod[300];
vector<int> decode(int mask) {
  vector<int> w;
  for (int(i) = ('A'); (i) <= ('Z'); ++i)
    w.push_back((mask / pprod[i - 1]) % prod[i]);
  return w;
}
int encode(vector<int> w) {
  int mask = 0;
  for (int(i) = ('A'); (i) <= ('Z'); ++i) mask += pprod[i - 1] * w[i - 'A'];
  return mask;
}
vector<int> addletter(vector<int> w, char l) {
  w[l - 'A']++;
  if (w[l - 'A'] == prod[l]) w[l - 'A'] = 0;
  return w;
}
int main() {
  ios_base::sync_with_stdio(0);
  long long n;
  int c;
  cin >> n >> c;
  while (c--) {
    string s;
    int mult;
    cin >> s >> mult;
    mults[s[0]].insert(mult);
  }
  int p = 1;
  for (int(i) = ('A'); (i) <= ('Z'); ++i) {
    prod[i] = 1;
    for (typeof(mults[i].begin()) it = mults[i].begin(); it != mults[i].end();
         it++)
      prod[i] *= *it;
    goodrests[i].insert(0);
    for (typeof(mults[i].begin()) it = mults[i].begin(); it != mults[i].end();
         it++)
      for (int x = *it; x < prod[i]; x += *it) goodrests[i].insert(x);
    p *= prod[i];
  }
  pprod['A' - 1] = 1;
  for (int(i) = ('A'); (i) <= ('Z'); ++i) pprod[i] = pprod[i - 1] * prod[i];
  ROZM = p;
  vector<vector<int> > T = zero();
  for (int(mask) = 0; (mask) < (p); ++(mask))
    for (int(l) = ('A'); (l) <= ('Z'); ++l) {
      if (mults[l].empty()) continue;
      int mask2 = encode(addletter(decode(mask), l));
      T[mask2][mask]++;
    }
  vector<vector<int> > Tpot = potega(T, n);
  long long res = 0;
  for (int(mask) = 0; (mask) < (p); ++(mask)) {
    vector<int> w = decode(mask);
    bool ok = 1;
    for (int(i) = ('A'); (i) <= ('Z'); ++i)
      if (!((goodrests[i]).find((w[i - 'A'])) != (goodrests[i]).end())) ok = 0;
    if (ok) res += Tpot[mask][0];
  }
  cout << (res % MOD) << endl;
}
