#include <bits/stdc++.h>
using namespace std;
long long N;
int M, T, ans;
int vis[125], sum[125];
int C[125], fr[125], rk[125];
int TC[125], tf[125];
int at[125], cnt[125];
char ss[2];
bool cmp(int a, int b) {
  return fr[a] < fr[b] || fr[a] == fr[b] && C[a] < C[b];
}
struct matrix {
  int c;
  int k[125][125];
  matrix operator*(matrix b) const {
    matrix n;
    int i, j, t;
    n.c = c;
    for (i = 0; i < c; i++)
      for (j = 0; j < T; j++)
        for (t = 0, n.k[i][j] = 0; t < T; t++)
          n.k[i][j] = (n.k[i][j] + k[i][t] * b.k[t][j]) % 12345;
    return n;
  }
} dp, one, st, ed;
matrix ksm(matrix x, long long t) {
  if (!t) return one;
  matrix tmp = ksm(x, t / 2);
  tmp = tmp * tmp;
  if (t & 1) tmp = tmp * x;
  return tmp;
}
int main() {
  int i, j, tmp, get, lt, flag;
  scanf("%I64d %d", &N, &M);
  for (i = 1, T = 1; i <= M; i++) {
    scanf("%s %d", ss, &C[i]);
    fr[i] = ss[0] - 'A' + 1;
    rk[i] = i, T *= C[i];
    vis[fr[i]] = 1;
  }
  sort(rk + 1, rk + 1 + M, cmp);
  for (i = 1; i <= M; i++) TC[i] = C[rk[i]], tf[i] = fr[rk[i]];
  memcpy(C, TC, sizeof(C)), memcpy(fr, tf, sizeof(tf));
  for (i = 1, sum[0] = 1; i <= M; i++) sum[i] = sum[i - 1] * C[i];
  for (i = 0; i < T; i++) {
    for (j = 1, lt = 1; j <= 26; j++) {
      if (!vis[j]) continue;
      for (lt, tmp = i; lt <= M && fr[lt] == j; lt++) {
        get = tmp / sum[lt - 1] % C[lt];
        tmp -= get * sum[lt - 1];
        get = (get + 1) % C[lt];
        tmp += get * sum[lt - 1];
      }
      st.k[i][tmp]++;
    }
  }
  st.c = T;
  dp.k[0][0] = 1, dp.c = 1;
  for (i = 0, one.c = T; i < T; i++) one.k[i][i] = 1;
  ed = ksm(st, N);
  dp = dp * ed;
  for (i = 0; i <= T; i++) {
    for (j = 1, lt = 1, tmp = i; j <= 26; j++) {
      if (!vis[j]) {
        flag = 1;
        continue;
      }
      for (lt, flag = 0; lt <= M && fr[lt] == j; lt++) {
        if (!(tmp % C[lt])) flag = 1;
        tmp /= C[lt];
      }
      if (!flag) break;
    }
    if (flag) ans = (ans + dp.k[0][i]) % 12345;
  }
  printf("%d\n", ans);
  return 0;
}
