#include <bits/stdc++.h>
using namespace std;
typedef int Matrix[150][150];
const int MAXN = 150;
const int INF = 0;
const int mod = 12345;
long long n;
int base, m;
void print(Matrix a) {
  for (int i = 0; i < base; ++i, puts("")) {
    for (int j = 0; j < base; ++j) printf("%d ", a[i][j]);
  }
  printf("\n\n");
}
void multi(Matrix a, Matrix b, Matrix &c) {
  Matrix tmp = {0};
  for (int k = 0; k < base; ++k)
    for (int i = 0; i < base; ++i) {
      if (a[i][k]) {
        for (int j = 0; j < base; ++j) {
          tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j] % mod) % mod;
        }
      }
    }
  memcpy(c, tmp, sizeof(tmp));
}
void fast(Matrix &a, long long b) {
  Matrix res = {0};
  for (int i = 0; i < base; ++i) {
    res[i][i] = 1;
  }
  while (b) {
    if (b & 1) multi(a, res, res);
    multi(a, a, a);
    b >>= 1;
  }
  memcpy(a, res, sizeof(res));
}
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
char s[100];
int num[30], g[30][300], b[30];
int fact[30];
Matrix one;
void toArray(int x, int b[]) {
  int h = base;
  for (int i = 26; i >= 0; --i) {
    if (num[i] <= 1)
      b[i] = 0;
    else {
      h /= num[i];
      b[i] = x / h;
      x %= h;
    }
  }
}
int toState(int b[]) {
  int res(0), h(1);
  for (int i = 0; i < 26; ++i) {
    if (num[i] > 1) {
      res += b[i] % num[i] * h;
      h *= num[i];
    }
  }
  return res;
}
void readin() {
  memset(g, 0, sizeof(g));
  for (int i = 0; i < 26; ++i) num[i] = 0, g[i][0] = 1;
  for (int i = 0, j; i < m; ++i) {
    scanf("%s%d", s, &j);
    if (j) {
      if (num[s[0] - 'A'] == 0) num[s[0] - 'A'] = 1;
      num[s[0] - 'A'] /= gcd(num[s[0] - 'A'], j);
      num[s[0] - 'A'] *= j;
      int k = j;
      for (j; j < MAXN; j += k) g[s[0] - 'A'][j] = 1;
    }
  }
  base = 1;
  memset(one, 0, sizeof(one));
  for (int i = 0; i < 26; ++i) {
    if (num[i] > 1) fact[i] = base;
    if (num[i]) base *= num[i];
  }
  for (int i = 0; i < base; ++i) {
    toArray(i, b);
    for (int j = 0; j < 26; ++j) {
      ++b[j];
      if (num[j] > 0) ++one[i][toState(b)];
      --b[j];
    }
  }
}
bool check(int x) {
  toArray(x, b);
  for (int i = 0; i < 26; ++i) {
    if (num[i] > 1 && !g[i][b[i]]) return 0;
  }
  return 1;
}
void slove() {
  fast(one, n);
  int ans(0);
  for (int i = 0; i < base; ++i) {
    if (check(i)) {
      ans = (ans + one[0][i]) % mod;
    }
  }
  printf("%d\n", ans);
}
int main() {
  while (~scanf("%I64d%d", &n, &m)) {
    readin();
    slove();
  }
  return 0;
}
