#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx,tune=native")
using namespace std;
const long long INF = 1e9 + 10;
const long long BINF = 1e18 + 10;
vector<long long> one;
long long lim = 1;
map<vector<long long>, long long> gt;
vector<long long> f[210];
long long md[26];
long long sum(vector<long long> a, vector<long long> b) {
  vector<long long> c;
  for (long long i = 0; i < ((long long)a.size()); i++) {
    c.push_back((a[i] + b[i]) % md[i]);
  }
  return gt[c];
}
vector<long long> mult(vector<long long> a, vector<long long> b,
                       long long mod) {
  vector<long long> res(((long long)a.size()));
  for (long long i = 0; i < lim; i++) {
    for (long long j = 0; j < lim; j++) {
      long long to = sum(f[i], f[j]);
      res[to] = (res[to] + a[i] * b[j]) % mod;
    }
  }
  return res;
}
vector<long long> b_pow(long long n, long long mod) {
  if (n == 1) {
    return one;
  }
  if (n & 1) {
    return mult(one, b_pow(n - 1, mod), mod);
  }
  vector<long long> mt = b_pow(n / 2, mod);
  return mult(mt, mt, mod);
}
vector<long long> have(26);
vector<vector<long long>> lol(26);
long long ff = 0;
void gen(long long ind, vector<long long> &cur) {
  if (ind == 26) {
    f[ff] = cur;
    gt[cur] = ff;
    one.push_back(0);
    ff++;
    return;
  }
  if (lol[ind].empty()) {
    gen(ind + 1, cur);
  }
  for (long long i = 0; i < have[ind]; i++) {
    cur.push_back(i);
    gen(ind + 1, cur);
    cur.pop_back();
  }
}
bool correct(vector<long long> x) {
  long long pnt = 0;
  for (auto it : x) {
    while (lol[pnt].empty()) {
      pnt++;
    }
    bool ok = false;
    for (auto it2 : lol[pnt]) {
      if (it % it2 == 0) {
        ok = true;
        break;
      }
    }
    if (!ok) {
      return false;
    }
    pnt++;
  }
  return true;
}
void source() {
  long long n, m;
  cin >> n >> m;
  if (n == 0) {
    cout << 1;
    exit(0);
  }
  if (m == 0) {
    cout << 0;
    exit(0);
  }
  for (long long i = 0; i < m; i++) {
    char c;
    long long val;
    cin >> c >> val;
    lim *= val;
    if (!have[c - 'A']) {
      have[c - 'A'] = val;
    } else {
      have[c - 'A'] *= val;
    }
    lol[c - 'A'].push_back(val);
  }
  long long cc = 0;
  for (long long i = 0; i < 26; i++) {
    if (!lol[i].empty()) {
      md[cc++] = have[i];
    }
  }
  vector<long long> em = {};
  gen(0, em);
  for (long long i = 0; i < cc; i++) {
    vector<long long> curr(cc);
    curr[i] = 1 % md[i];
    one[gt[curr]]++;
  }
  vector<long long> res = b_pow(n, 12345);
  long long ans = 0;
  for (long long i = 0; i < ff; i++) {
    if (correct(f[i])) {
      ans = (ans + res[i]) % 12345;
    }
  }
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  source();
  return 0;
}
