#include <bits/stdc++.h>
using namespace std;
typedef int matrix[130][130];
long long n;
vector<int> v[130];
int k, q[30], d, f[30], h[130], len[30], r[30], ans;
matrix a, b, t;
char c;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void mul(matrix a, matrix b) {
  for (int i = 0; i < len[0]; i++)
    for (int j = 0; j < len[0]; j++) {
      t[i][j] = 0;
      for (int k = 0; k < len[0]; k++)
        t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % 12345;
    }
  for (int i = 0; i < len[0]; i++)
    for (int j = 0; j < len[0]; j++) a[i][j] = t[i][j];
}
void pow(long long n) {
  for (int i = 0; i < len[0]; i++) a[i][i] = 1;
  for (int i = 0; n >> i; i++) {
    if ((n >> i) & 1) mul(a, b);
    mul(b, b);
  }
}
int main() {
  scanf("%I64d%d", &n, &k);
  for (int i = 0; i < 26; i++) q[i] = 1;
  for (int i = 0; i < k; i++)
    scanf(" %c%d", &c, &d), c -= 'A', q[c] *= d / gcd(d, q[c]),
        f[c] = 1, v[c].push_back(d);
  len[26] = 1;
  for (int j = 25; j >= 0; j--) len[j] = len[j + 1] * q[j];
  for (int j = 0; j < len[0]; j++) {
    for (int i = 0; i < 26; i++) r[i] = j / len[i + 1] % q[i];
    h[j] = 1;
    for (int i = 0; i < 26; i++)
      if (v[i].size()) {
        bool fg = 0;
        for (int d : v[i]) fg |= (r[i] % d == 0);
        h[j] &= fg;
      }
    for (int i = 0; i < 26; i++)
      if (f[i])
        b[j][(r[i] + 1 == q[i]) ? j + len[i + 1] - len[i] : j + len[i + 1]]++;
  }
  pow(n);
  for (int i = 0; i < len[0]; i++) ans += h[i] * a[0][i];
  printf("%d\n", ans % 12345);
}
