#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long r = 0, f = 0;
  char c;
  while (!isdigit(c = getchar())) f |= (c == '-');
  while (isdigit(c)) r = (r << 1) + (r << 3) + (c ^ 48), c = getchar();
  return f ? -r : r;
}
inline char get_c() {
  char c;
  while (!isalpha(c = getchar()))
    ;
  return c;
}
int N = 1;
long long n;
int cnt, mul[33];
long long ans, f[222], a[222][222], c[222][222];
vector<int> m[33];
inline void mulself() {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
        (c[i][j] += a[i][k] * a[k][j] % 12345) %= 12345;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      a[i][j] = c[i][j];
      c[i][j] = 0;
    }
}
inline void multi() {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) (c[0][i] += f[j] * a[i][j] % 12345) %= 12345;
  for (int i = 0; i < N; i++) {
    f[i] = c[0][i];
    c[0][i] = 0;
  }
}
int main() {
  n = read(), cnt = read();
  for (int i = 1; i <= cnt; i++) {
    int t = get_c() - 'A' + 1;
    int val = read();
    m[t].push_back(val);
    if (!mul[t]) mul[t] = 1;
    mul[t] *= val;
  }
  for (int i = 1; i <= 26; i++)
    if (mul[i]) N *= mul[i];
  N++;
  for (int i = 0; i < N; i++) {
    int num = i;
    long long mult = 1;
    for (int j = 26; j >= 1; j--) {
      if (!mul[j]) continue;
      int tot = num % mul[j];
      int s = i - tot * mult;
      tot++;
      tot %= mul[j];
      s += tot * mult;
      num /= mul[j];
      mult *= mul[j];
      a[s][i]++;
    }
  }
  f[0] = 1;
  for (; n; n >>= 1) {
    if (n & 1) multi();
    mulself();
  }
  for (int i = 0; i < N; i++) {
    int num = i;
    bool ok = 1;
    for (int j = 26; j >= 1; j--) {
      if (!mul[j]) continue;
      int tot = num % mul[j];
      bool b = 0;
      for (int k = 0; k < (int)m[j].size(); k++) b |= ((tot % m[j][k]) == 0);
      ok &= b;
      num /= mul[j];
    }
    if (ok) (ans += f[i]) %= 12345;
  }
  printf("%lld\n", ans);
  return 0;
}
