#include <bits/stdc++.h>
using namespace std;
long long n, m, mode[30], all = 1, dp[210], c[210][210], ans = 0;
vector<long long> q[30];
long long gi() {
  long long w = 0, f = 1;
  char ch;
  while (!isdigit(ch)) {
    f = ch == '-' ? -1 : 1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    w = (w << 1) + (w << 3) + ch - 48;
    ch = getchar();
  }
  return w * f;
}
char getc() {
  char ch = 'a';
  while (ch < 'A' || ch > 'Z') ch = getchar();
  return ch;
}
void mulself() {
  long long tmp[210][210];
  for (long long i = 0; i < all; i++) {
    for (long long j = 0; j < all; j++) {
      tmp[i][j] = 0;
    }
  }
  for (long long i = 0; i < all; i++) {
    for (long long j = 0; j < all; j++) {
      for (long long k = 0; k < all; k++) {
        tmp[i][j] = (tmp[i][j] + c[i][k] * c[k][j] % 12345) % 12345;
      }
    }
  }
  for (long long i = 0; i < all; i++) {
    for (long long j = 0; j < all; j++) {
      c[i][j] = tmp[i][j];
    }
  }
}
void mul() {
  long long tmp[210];
  for (long long i = 0; i < all; i++) tmp[i] = 0;
  for (long long i = 0; i < all; i++) {
    for (long long j = 0; j < all; j++) {
      tmp[i] = (tmp[i] + dp[j] * c[j][i] % 12345) % 12345;
    }
  }
  for (long long i = 0; i < all; i++) {
    dp[i] = tmp[i];
  }
}
signed main() {
  memset(mode, 0, sizeof(mode));
  n = gi();
  m = gi();
  for (long long i = 1; i <= m; i++) {
    long long t = getc() - 'A' + 1;
    long long x = gi();
    q[t].push_back(x);
    if (!mode[t]) mode[t] = 1;
    mode[t] *= x;
    all *= x;
  }
  all++;
  for (long long i = 0; i < all; i++) {
    long long tmp = i, tmpmul = 1;
    for (long long j = 26; j >= 1; j--) {
      if (!mode[j]) continue;
      long long num = tmp % mode[j], ver;
      ver = i - num * tmpmul;
      num++;
      num %= mode[j];
      ver = ver + num * tmpmul;
      tmp /= mode[j];
      tmpmul *= mode[j];
      c[i][ver]++;
    }
  }
  dp[0] = 1;
  while (n) {
    if (n & 1) mul();
    mulself();
    n >>= 1;
  }
  for (long long i = 0; i < all; i++) {
    long long tmp = i, flag = 1;
    for (long long j = 26; j >= 1; j--) {
      if (!mode[j]) continue;
      long long num = tmp % mode[j];
      tmp /= mode[j];
      bool flag1 = 0;
      for (long long k = 0; k < q[j].size(); k++) {
        if (num % q[j][k] == 0) flag1 = 1;
      }
      if (flag1 == 0) flag = 0;
    }
    if (flag) {
      ans = (ans + dp[i]) % 12345;
    }
  }
  cout << ans << "\n";
}
