#include <bits/stdc++.h>
using namespace std;
const int MS = 125, modu = 12345, CS = 1050, VS = 27;
typedef int matrix[MS][MS];
pair<int, int> R[CS], rg[VS];
int rcnt, msize;
bool avaliable[VS];
inline void decompose(int mask, int dest[]) {
  for (int i = 1; i <= rcnt; ++i) {
    dest[i] = mask % R[i].second;
    mask /= R[i].second;
  }
}
inline int compose(int src[]) {
  int res(0);
  for (int i = rcnt; i >= 1; --i) {
    res += src[i];
    res *= i == 1 ? 1 : R[i - 1].second;
  }
  return res;
}
void buildMatrix(matrix M) {
  for (int i = 0; i < msize; ++i) {
    int cnt[CS];
    decompose(i, cnt);
    for (int t = 1; t <= 26; ++t)
      if (avaliable[t]) {
        for (int j = rg[t].first; j <= rg[t].second; ++j)
          cnt[j] = (cnt[j] + 1) % R[j].second;
        int z = compose(cnt);
        ++M[i][z];
        for (int j = rg[t].first; j <= rg[t].second; ++j)
          cnt[j] = (cnt[j] - 1 + R[j].second) % R[j].second;
      }
  }
}
void mult(matrix A, matrix B, matrix C) {
  matrix R;
  for (int i = 0; i < msize; ++i)
    for (int j = 0; j < msize; ++j) {
      R[i][j] = 0;
      for (int k = 0; k < msize; ++k)
        R[i][j] = (R[i][j] + A[i][k] * B[k][j]) % modu;
    }
  for (int i = 0; i < msize; ++i)
    for (int j = 0; j < msize; ++j) C[i][j] = R[i][j];
}
long long ccnt;
matrix A, B, C, M;
int solve() {
  scanf("%I64d%d", &ccnt, &rcnt);
  for (int i = 1; i <= rcnt; ++i) {
    char s[20];
    scanf("%s", s);
    scanf("%d", &R[i].second);
    R[i].first = s[0] - 'A' + 1;
  }
  sort(R + 1, R + 1 + rcnt);
  rcnt = unique(R + 1, R + 1 + rcnt) - (R + 1);
  for (int i = 1; i <= rcnt; ++i) {
    avaliable[R[i].first] = 1;
    if (rg[R[i].first].first > 0)
      rg[R[i].first].second = i;
    else
      rg[R[i].first].first = rg[R[i].first].second = i;
  }
  msize = 1;
  for (int i = 1; i <= rcnt; ++i) msize *= R[i].second;
  if (msize > MS) throw;
  buildMatrix(M);
  for (int i = 0; i < msize; ++i)
    for (int j = 0; j < msize; ++j) A[i][j] = M[i][j], C[i][j] = bool(i == j);
  for (; ccnt; ccnt >>= 1, mult(A, A, A))
    if (ccnt & 1) mult(C, A, C);
  int res(0);
  for (int i = 0; i < msize; ++i) {
    int cnt[CS], valid(1);
    decompose(i, cnt);
    for (int t = 1; valid && t <= 26; ++t)
      if (avaliable[t]) {
        bool f = false;
        for (int j = rg[t].first; !f && j <= rg[t].second; ++j)
          if (!cnt[j]) f = true;
        if (!f) valid = 0;
      }
    if (valid) res = (res + C[0][i]) % modu;
  }
  printf("%d\n", res);
  return 0;
}
int main() { return solve(); }
