#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  int num[140][140];
};
int num[30][30], Mul[30], size[30], v[30], b[140];
char str[10001];
long long c;
int n, m;
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
Matrix operator*(Matrix& a, Matrix& b) {
  Matrix c;
  memset(c.num, 0, sizeof(c.num));
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n; k++)
        c.num[i][j] += a.num[i][k] * b.num[k][j], c.num[i][j] %= 12345;
  return c;
}
Matrix Ksm(Matrix get, long long T) {
  Matrix t, ans;
  memset(t.num, 0, sizeof(t.num));
  memset(ans.num, 0, sizeof(ans.num));
  ans.num[1][1] = 1;
  t = get;
  while (T) {
    if (T & 1) ans = ans * t;
    t = t * t;
    T >>= 1;
  }
  return ans;
}
int work() {
  int ans = 0;
  Matrix mat;
  Mul[0] = 1;
  for (int i = 1; i <= 26; i++) Mul[i] = Mul[i - 1] * size[i];
  n = Mul[26];
  for (int i = 1; i <= n; i++) {
    b[i] = 1;
    for (int j = 1; j <= 26; j++)
      if (v[j]) {
        int flag = 0, tmp = i + Mul[j - 1] - 1;
        if (((i - 1) / Mul[j - 1] + 1) % size[j] == 0) tmp -= Mul[j];
        ++mat.num[i][tmp + 1];
        for (int k = 1; k <= v[j]; k++)
          if (((i - 1) / Mul[j - 1]) % num[j][k] == 0) flag = 1;
        b[i] &= flag;
      }
  }
  mat = Ksm(mat, c);
  for (int i = 1; i <= n; i++)
    if (b[i]) ans += mat.num[1][i], ans %= 12345;
  return ans;
}
int main() {
  int x;
  scanf("%I64d %d", &c, &m);
  for (int i = 1; i <= 26; i++) size[i] = 1;
  for (int i = 1; i <= m; i++) {
    scanf("%s", str);
    int get = str[0] - 'A' + 1;
    scanf("%d", &x);
    size[get] *= x / gcd(x, size[get]);
    num[get][++v[get]] = x;
  }
  printf("%d\n", work() % 12345);
  return 0;
}
