#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  int m[125][125];
  Matrix() { memset(m, 0, sizeof(m)); }
} Init, Ret;
Matrix mul(Matrix a, Matrix b, int n) {
  Matrix ans;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++)
        ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j]) % 12345;
  return ans;
}
Matrix PowMod(Matrix a, long long m, int n) {
  Matrix ans;
  for (int i = 0; i < n; i++) ans.m[i][i] = 1;
  while (m) {
    if (m & 1) ans = mul(ans, a, n);
    a = mul(a, a, n);
    m /= 2;
  }
  return ans;
}
void Debug(Matrix a, int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) printf("%d ", a.m[i][j]);
    printf("\n");
  }
}
long long n;
int c, flag[26], cnt, val[1005], id[1005];
void Bulid() {
  memset(Init.m, 0, sizeof(Init.m));
  for (int i = 0; i < cnt; i++) {
    int mod[c], tmp = i;
    for (int j = 0; j < c; j++) {
      mod[j] = tmp % val[j];
      tmp /= val[j];
    }
    for (int j = 0; j < 26; j++) {
      if (flag[j]) {
        for (int k = 0; k < c; k++) {
          if (id[k] == j) {
            mod[k]++;
            if (mod[k] >= val[k]) mod[k] -= val[k];
          }
        }
        int now = 0;
        for (int k = c - 1; k >= 0; k--) now = now * val[k] + mod[k];
        Init.m[i][now]++;
        for (int k = 0; k < c; k++) {
          if (id[k] == j) {
            mod[k]--;
            if (mod[k] < 0) mod[k] += val[k];
          }
        }
      }
    }
  }
  for (int i = 0; i < cnt; i++)
    for (int j = 0; j < cnt; j++) Init.m[i][j] %= 12345;
}
bool check(int k) {
  bool ok[26];
  memset(ok, false, sizeof(ok));
  for (int i = 0; i < c; i++) {
    int tmp = k % val[i];
    k /= val[i];
    if (tmp == 0) ok[id[i]] = true;
  }
  for (int i = 0; i < 26; i++)
    if (flag[i] && !ok[i]) return false;
  return true;
}
char str[10];
int main() {
  while (scanf("%I64d%d", &n, &c) != EOF) {
    cnt = 1;
    memset(flag, 0, sizeof(flag));
    for (int i = 0; i < c; i++) {
      scanf("%s%d", str, &val[i]);
      id[i] = str[0] - 'A';
      cnt *= val[i];
      flag[id[i]] = 1;
    }
    Bulid();
    Ret = PowMod(Init, n, cnt);
    int ans = 0;
    for (int i = 0; i < cnt; i++) {
      if (check(i)) {
        ans += Ret.m[0][i];
      }
    }
    printf("%d\n", ans % 12345);
  }
  return 0;
}
