#include <bits/stdc++.h>
using namespace std;
struct matrix {
  int a[130][130];
};
struct matrix g, f, e;
struct unit {
  int x;
  vector<int> w;
};
struct unit a[30];
long long n;
int m, ans;
int b[30], c[30];
const int mod = 12345;
bool cmp(struct unit aa, struct unit bb) { return aa.x > bb.x; }
int gcd(int i, int j) {
  if (j == 0)
    return i;
  else
    return gcd(j, i % j);
}
matrix operator*(matrix aa, matrix bb) {
  matrix ret;
  int i, j, k;
  memset(ret.a, 0, sizeof(ret.a));
  for (i = 0; i <= 123; i++)
    for (k = 0; k <= 123; k++)
      if (aa.a[i][k]) {
        for (j = 0; j <= 123; j++)
          ret.a[i][j] = (ret.a[i][j] + aa.a[i][k] * bb.a[k][j] % mod) % mod;
      }
  return ret;
}
matrix fpow(long long j) {
  matrix ret = e, t;
  t = g;
  while (j > 0) {
    if (j & 1) ret = ret * t;
    t = t * t;
    j /= 2;
  }
  return ret;
}
int main() {
  int i, j, x, s, s1, flag;
  char ch[2];
  for (i = 0; i <= 123; i++) e.a[i][i] = 1;
  scanf("%I64d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%s%d", ch, &x);
    if (a[ch[0] - 64].x == 0)
      a[ch[0] - 64].x = x;
    else
      a[ch[0] - 64].x = a[ch[0] - 64].x * x / gcd(a[ch[0] - 64].x, x);
    a[ch[0] - 64].w.push_back(x);
  }
  sort(a + 1, a + 26 + 1, cmp);
  for (i = 1; i <= 26; i++)
    if (a[i].x == 0) {
      m = i - 1;
      break;
    }
  for (i = m; i >= 1; i--) {
    b[i] = 1;
    for (j = i + 1; j <= m; j++) b[i] += (a[j].x - 1) * b[j];
  }
  while (c[0] == 0) {
    s = 0;
    for (i = 1; i <= m; i++) s += c[i] * b[i];
    for (i = 1; i <= m; i++) {
      if (c[i] == a[i].x - 1)
        s1 = s - b[i] * (a[i].x - 1);
      else
        s1 = s + b[i];
      g.a[s][s1]++;
    }
    i = m;
    while (c[i] == a[i].x - 1) {
      c[i] = 0;
      i--;
    }
    c[i]++;
  }
  f = fpow(n);
  memset(c, 0, sizeof(c));
  while (c[0] == 0) {
    s = 0;
    flag = 1;
    for (i = 1; i <= m; i++) s += c[i] * b[i];
    for (i = 1; i <= m; i++) {
      flag = 0;
      for (j = 0; j < a[i].w.size(); j++)
        if (c[i] % a[i].w[j] == 0) {
          flag = 1;
          break;
        }
      if (!flag) break;
    }
    if (flag) ans = (ans + f.a[0][s]) % mod;
    i = m;
    while (c[i] == a[i].x - 1) {
      c[i] = 0;
      i--;
    }
    c[i]++;
  }
  cout << ans << endl;
  return 0;
}
