#include <bits/stdc++.h>
using namespace std;
inline int _pow(int a, int b) {
  int tmp = 1;
  for (; b; b >>= 1) {
    if (b & 1) tmp = (long long)tmp * a % 12345;
    a = (long long)a * a % 12345;
  }
  return tmp;
}
template <class T>
inline void R(T &xx) {
  xx = 0;
  char ch = getchar();
  bool F = 0;
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') F = 1, ch = getchar();
  while (ch >= '0' && ch <= '9')
    xx = xx + xx + (xx << 3) + ch - 48, ch = getchar();
  if (F) xx = -xx;
}
int S = 1, m, b[1005], d[1005];
long long n;
bool c[26], f[130];
char a[1005][2];
struct mat {
  int a[130][130];
  mat() { memset(a, 0, sizeof(a)); }
  inline void operator*=(const mat &b) {
    mat c;
    for (int i = 0; i < (int)(S); i++)
      for (int j = 0; j < (int)(S); j++) {
        long long t = 0;
        for (int k = 0; k < (int)(S); k++) t += (long long)a[i][k] * b.a[k][j];
        c.a[i][j] = t % 12345;
      }
    memcpy(a, c.a, sizeof(a));
  }
} base, A;
mat _pow(mat a, long long b) {
  mat tmp = base;
  for (; b; b >>= 1) {
    if (b & 1) tmp *= a;
    a *= a;
  }
  return tmp;
}
int main() {
  for (int i = 0; i < (int)(128); i++) base.a[i][i] = 1;
  R(n), R(m);
  for (int i = (1); i <= (m); i++)
    scanf("%s", a[i]), R(b[i]), S *= b[i], c[a[i][0] -= 65] = 1;
  for (int i = 0; i < (int)(S); i++) {
    for (int j = m, x = i; j; x /= b[j--]) d[j] = x % b[j];
    f[i] = 1;
    for (int k = 0; k < (int)(26); k++)
      if (c[k]) {
        int x = 0;
        bool ok = 0;
        for (int j = (1); j <= (m); j++) {
          int y = d[j];
          if (k == a[j][0]) ok |= !d[j], (y += 1) %= b[j];
          (x *= b[j]) += y;
        }
        A.a[i][x]++, f[i] &= ok;
      }
  }
  A = _pow(A, n);
  int ans = 0;
  for (int i = 0; i < (int)(S); i++)
    if (f[i]) (ans += A.a[0][i]) %= 12345;
  printf("%d\n", ans);
  return 0;
}
