#include <bits/stdc++.h>
using namespace std;
const int N = 155, oo = 12345;
int m, x, y, now, ans, a[N][N], b[N][N], c[N], e[N], s[N], res[N];
bool d[N][N], f[N];
char type[5];
vector<int> p(26);
map<vector<int>, int> h;
void mul1() {
  memset(c, 0, sizeof(c));
  for (int i = 0; i < now; i++)
    for (int j = 0; j < now; j++) c[i] = (a[i][j] * res[j] + c[i]) % oo;
  memcpy(res, c, sizeof(res));
}
void mul() {
  memset(b, 0, sizeof(b));
  for (int i = 0; i < now; i++)
    for (int j = 0; j < now; j++)
      for (int k = 0; k < now; k++)
        b[i][j] = (a[i][k] * a[k][j] + b[i][j]) % oo;
  memcpy(a, b, sizeof(a));
}
int dfs(vector<int> c) {
  typeof(h.end()) it = h.find(c);
  if (it != h.end()) return it->second;
  int tmp = now++;
  h[c] = tmp;
  f[tmp] = 1;
  vector<int> b;
  for (int i = 0; i < 26; i++)
    if (e[i]) f[tmp] &= d[i][c[i]];
  for (int i = 0; i < 26; i++)
    if (e[i]) b = c, b[i] = (b[i] + 1) % s[i], a[dfs(b)][tmp]++;
  return tmp;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() {
  long long n;
  cin >> n >> m, res[0] = 1;
  for (int i = 1; i <= m; i++)
    scanf("%s%d", type, &y), x = type[0] - 65, d[x][y] = 1, e[x] = 1;
  for (int i = 0; i < 26; i++) {
    s[i] = 1;
    for (int j = 0; j < 123; j++)
      if (d[i][j]) s[i] *= j / gcd(s[i], j);
    for (int j = 122; j; j--)
      if (d[i][j])
        for (int k = j; k < 123; k += j) d[i][k] = 1;
    d[i][0] = 1;
  }
  dfs(p);
  while (n) {
    if (n & 1) mul1();
    n /= 2;
    mul();
  }
  for (int i = 0; i < now; i++)
    if (f[i]) ans = (ans + res[i]) % oo;
  printf("%d\n", ans);
  return 0;
}
