#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1, c = getchar();
  while (c < 48) c == '-' && (f = -1), c = getchar();
  while (c > 47) x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int MAXN = 1005;
const int mod = 12345;
struct node {
  char c;
  int k;
} a[MAXN];
int chk[MAXN], vis[MAXN];
long long n, m, ans, r = 1;
struct Matrix {
  int s[155][155];
  Matrix() { memset(s, 0, sizeof(s)); }
  int *operator[](int i) { return s[i]; }
} mat, Q;
Matrix operator*(Matrix a, Matrix b) {
  Matrix c;
  for (int i = 0; i < r; ++i)
    for (int j = 0; j < r; ++j)
      for (int l = 0; l < r; ++l)
        c[i][j] = (c[i][j] + 1ll * a[i][l] * b[l][j]) % mod;
  return c;
}
Matrix qpow(Matrix x, long long k) {
  Matrix res = x;
  for (long long i = k - 1; i; i >>= 1, x = x * x)
    if (i & 1) res = res * x;
  return res;
}
void dfs1(int p, char c, int x, int y) {
  if (p > m) return ++Q[x][y], void();
  for (int i = 0; i < a[p].k; ++i)
    dfs1(p + 1, c, x * a[p].k + i, y * a[p].k + (i + (a[p].c == c)) % a[p].k);
}
void dfs2(int p, int st) {
  if (p > m) {
    int flag = 1;
    for (char i = 'A'; i <= 'Z'; ++i)
      if (vis[i] && !chk[i]) {
        flag = 0;
        break;
      }
    if (flag) ans = (ans + mat[0][st]) % mod;
    return;
  }
  int t = chk[a[p].c];
  for (int i = 1; i < a[p].k; ++i) dfs2(p + 1, st * a[p].k + i);
  chk[a[p].c] = 1, dfs2(p + 1, st * a[p].k), chk[a[p].c] = t;
}
int main(int argc, char const *argv[]) {
  n = read(), m = read();
  if (n == 0) return puts("1"), 0;
  auto getc = [](char c = 0) { return cin >> c, c; };
  for (int i = 1; i <= m; ++i) vis[a[i].c = getc()] = 1, r *= (a[i].k = read());
  for (char i = 'A'; i <= 'Z'; ++i)
    if (vis[i]) dfs1(1, i, 0, 0);
  mat[0][0] = 1;
  mat = mat * qpow(Q, n);
  dfs2(1, 0);
  printf("%d\n", ans);
  return 0;
}
