#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:65777216")
using namespace std;
const int mod = 12345;
const int M2 = mod * mod;
long long n;
int c;
int t[1111], k[1111];
vector<int> v[26];
int g[26];
int G;
struct M {
  int a[123][123];
  M() { memset(a, 0, sizeof(a)); }
  M pow(M &s) {
    M r;
    for (int i(0); i < (123); i++)
      for (int j(0); j < (123); j++) {
        int x = 0;
        for (int k(0); k < (123); k++) {
          x += a[i][k] * s.a[k][j];
          if (x >= M2) x -= M2;
        }
        r.a[i][j] = x % mod;
      }
    return r;
  }
};
int gcd(int a, int b) {
  while (a && b)
    if (a > b)
      a %= b;
    else
      b %= a;
  return a + b;
}
M qp(M m, long long n) {
  M t;
  for (int i(0); i < (123); i++) t.a[i][i] = 1;
  while (n) {
    if (n & 1) t = t.pow(m);
    m = m.pow(m);
    n >>= 1;
  }
  return t;
}
bool good(int i) {
  vector<int> t(26);
  int curr = i;
  for (int j(0); j < (26); j++)
    if (g[j]) {
      t[j] = curr % g[j];
      curr /= g[j];
    }
  for (int j(0); j < (26); j++)
    if (g[j]) {
      bool f = 0;
      for (int k(0); k < (v[j].size()); k++)
        if (t[j] % v[j][k] == 0) {
          f = 1;
          break;
        }
      if (!f) return 0;
    }
  return 1;
}
int main() {
  cin >> n;
  cin >> c;
  for (int i(0); i < (c); i++) {
    char T;
    scanf(" %c %d", &T, &k[i]);
    t[i] = T - 'A';
    v[t[i]].push_back(k[i]);
  }
  G = 1;
  for (int i(0); i < (26); i++) {
    sort((v[i]).begin(), (v[i]).end()),
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
    if (v[i].size()) {
      g[i] = v[i][0];
      for (int j(0); j < (v[i].size()); j++)
        g[i] = g[i] * v[i][j] / gcd(g[i], v[i][j]);
      G *= g[i];
    }
  }
  M m;
  for (int i(0); i < (G); i++) {
    vector<int> t(26);
    int curr = i;
    for (int j(0); j < (26); j++)
      if (g[j]) {
        t[j] = curr % g[j];
        curr /= g[j];
      }
    for (int j(0); j < (26); j++)
      if (g[j]) {
        t[j]++;
        if (t[j] >= g[j]) t[j] = 0;
        int val = 0;
        for (int q = 25; q >= 0; q--)
          if (g[q]) {
            val = val * g[q] + t[q];
          }
        m.a[i][val]++;
        t[j]--;
        if (t[j] < 0) t[j] += g[j];
      }
  }
  m = qp(m, n);
  int res = 0;
  for (int i(0); i < (G); i++) {
    int val = m.a[i][0];
    if (good(i)) {
      res += val;
      res %= mod;
    }
  }
  cout << res << endl;
  return 0;
}
