#include <bits/stdc++.h>
const int oo = 12345;
bool flag;
int M, s, tmp, i, j, k, Ans;
int A[30], B[30];
int C[125], c[125], D[125][125], d[125][125];
int W[1005];
char P[1005];
long long N;
void Mul1() {
  int i, j;
  for (i = 0; i < s; ++i) c[i] = 0;
  for (i = 0; i < s; ++i)
    if (C[i])
      for (j = 0; j < s; ++j)
        if (D[i][j]) c[j] = (c[j] + C[i] * D[i][j]) % oo;
  for (i = 0; i < s; ++i) C[i] = c[i];
}
void Mul2() {
  int i, j, k;
  for (i = 0; i < s; ++i)
    for (j = 0; j < s; ++j) d[i][j] = 0;
  for (i = 0; i < s; ++i)
    for (j = 0; j < s; ++j)
      if (D[i][j])
        for (k = 0; k < s; ++k)
          if (D[j][k]) d[i][k] = (d[i][k] + D[i][j] * D[j][k]) % oo;
  for (i = 0; i < s; ++i)
    for (j = 0; j < s; ++j) D[i][j] = d[i][j];
}
void Mul(long long N) {
  for (; N;) {
    if (N & 1) Mul1();
    N /= 2, Mul2();
  }
}
int main() {
  scanf("%I64d%d", &N, &M);
  s = 1;
  for (i = 1; i <= M; ++i) {
    for (P[i] = getchar(); P[i] < 'A' || P[i] > 'Z'; P[i] = getchar())
      ;
    P[i] -= 'A';
    if (!B[P[i]]) B[P[i]] = 1;
    scanf("%d", &W[i]);
    B[P[i]] *= W[i];
    s *= W[i];
  }
  for (i = 0; i < s; ++i) {
    for (j = 0; j < 26; ++j) A[j] = -1;
    tmp = i;
    for (j = 0; j < 26; ++j)
      if (B[j]) {
        A[j] = tmp % B[j];
        tmp /= B[j];
      }
    for (j = 0; j < 26; ++j)
      if (B[j]) {
        ++A[j];
        tmp = 0;
        for (k = 25; k >= 0; --k)
          if (B[k]) {
            tmp = tmp * B[k];
            tmp = tmp + A[k] % B[k];
          }
        ++D[i][tmp];
        --A[j];
      }
  }
  C[0] = 1;
  Mul(N);
  for (i = 0; i < s; ++i) {
    for (j = 0; j < 26; ++j) A[j] = -1;
    tmp = i;
    for (j = 0; j < 26; ++j)
      if (B[j]) {
        A[j] = tmp % B[j];
        tmp /= B[j];
      }
    for (j = 1; j <= M; ++j)
      if (A[P[j]] % W[j] == 0) A[P[j]] = 0;
    flag = 1;
    for (j = 0; j < 26; ++j)
      if (A[j] > 0) flag = 0;
    if (flag) Ans = (Ans + C[i]) % oo;
  }
  printf("%d\n", Ans);
  return 0;
}
