#include <bits/stdc++.h>
using namespace std;
const int MAXL = 123, MOD = 12345, MAXN = 26 + 5, CNTALP = 26;
struct Matrix {
  int num[MAXL][MAXL];
  Matrix() { memset(num, 0, sizeof(num)); }
  Matrix operator*(const Matrix &b) const {
    Matrix c;
    for (int i = 0; i < MAXL; ++i)
      for (int j = 0; j < MAXL; ++j)
        for (int k = 0; k < MAXL; ++k)
          c.num[i][j] = (c.num[i][j] + num[i][k] * b.num[k][j]) % MOD;
    return c;
  }
  void Print() const {
    for (int i = 0; i < MAXL; ++i, puts(""))
      for (int j = 0; j < MAXL; ++j) printf("%d ", num[i][j]);
  }
} B;
Matrix Power(Matrix a, long long b) {
  Matrix d;
  for (int i = 0; i < MAXL; ++i) d.num[i][i] = 1;
  for (; b; d = (b & 1) ? d * a : d, a = a * a, b /= 2)
    ;
  return d;
}
int pdt[MAXN], b[MAXN], m, N;
long long n;
bool used[MAXN];
vector<int> fac[MAXN];
char str[10];
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
int lcm(int x, int y) { return x * y / gcd(x, y); }
void init() {
  cin >> n >> m;
  for (int i = 0; i < CNTALP; ++i) b[i] = 1;
  memset(used, 0, sizeof(used));
  for (int i = 1; i <= m; ++i) {
    int x, id;
    scanf("%s%d", str, &x);
    id = str[0] - 'A';
    used[id] = true;
    fac[id].push_back(x);
    b[id] = lcm(b[id], x);
  }
  pdt[0] = 1;
  for (int i = 1; i <= CNTALP; ++i) pdt[i] = pdt[i - 1] * b[i - 1];
  N = pdt[CNTALP];
}
void solve() {
  for (int i = 0; i < CNTALP; ++i)
    if (used[i])
      for (int k = 0; k < N; ++k) {
        int tmp = k % pdt[i + 1] / pdt[i];
        ++B.num[k][k - tmp * pdt[i] + (tmp + 1) % b[i] * pdt[i]];
      }
  B = Power(B, n);
  int CC = 0;
  for (int i = 0; i < N; ++i) {
    bool flag = true;
    for (int j = 0; j < CNTALP; ++j)
      if (used[j]) {
        bool flag1 = true;
        for (int k = 0; k < (int)fac[j].size(); ++k)
          if (i % pdt[j + 1] / pdt[j] % fac[j][k] == 0) {
            flag1 = false;
            break;
          }
        if (flag1) {
          flag = false;
          break;
        }
      }
    if (flag) CC = (CC + B.num[0][i]) % MOD;
  }
  cout << CC << endl;
}
int main() {
  init();
  solve();
  fclose(stdin);
  fclose(stdout);
  return 0;
}
