#include <bits/stdc++.h>
using namespace std;
const int mod = 12345;
typedef int matrix[150][150];
int c;
long long n;
void mul(matrix c, matrix a, matrix b, int n) {
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      c[i][j] = 0;
      for (int k = 0; k < n; k++)
        c[i][j] += (long long)a[i][k] * (long long)b[k][j] % mod;
      c[i][j] %= mod;
    }
}
void pow(matrix c, matrix a, int n, long long p) {
  matrix d;
  memset(c, 0, sizeof(matrix));
  for (int i = 0; i < n; i++) c[i][i] = 1;
  memcpy(d, a, sizeof(matrix));
  for (long long i = 1; i <= p; i <<= 1) {
    matrix t;
    if (i & p) {
      mul(t, c, d, n);
      memcpy(c, t, sizeof(matrix));
    }
    mul(t, d, d, n);
    memcpy(d, t, sizeof(matrix));
  }
}
int prod[26], pros[27];
vector<int> fact[26];
vector<int> decode(int s) {
  vector<int> r(26);
  for (int i = 0; i < 26; i++) {
    r[i] = s % prod[i];
    s /= prod[i];
  }
  return r;
}
int encode(vector<int> &v) {
  int r = 0;
  for (int i = 0; i < 26; i++) r += v[i] * pros[i];
  return r;
}
int main() {
  scanf("%I64d%d", &n, &c);
  fill(prod, prod + 26, 1);
  for (int i = 0; i < c; i++) {
    char str[1024];
    scanf("%s", str);
    int x, y = str[0] - 'A';
    scanf("%d", &x);
    prod[y] *= x;
    fact[y].push_back(x);
  }
  if (n == 0) {
    puts("1");
    return 0;
  }
  pros[0] = 1;
  for (int i = 1; i <= 26; i++) pros[i] = pros[i - 1] * prod[i - 1];
  int m = pros[26];
  matrix a = {}, b;
  for (int i = 0; i < m; i++) {
    vector<int> u = decode(i);
    for (int j = 0; j < 26; j++) {
      if (fact[j].size() == 0) continue;
      vector<int> v = u;
      v[j] = (v[j] + 1) % prod[j];
      a[i][encode(v)]++;
    }
  }
  pow(b, a, m, n);
  int ans = 0;
  for (int i = 0; i < m; i++) {
    vector<int> u = decode(i);
    bool ok = true;
    for (int j = 0; j < 26; j++) {
      if (fact[j].size() == 0) continue;
      vector<int> &curr = fact[j];
      bool flag = true;
      for (int k = 0; k < (int)curr.size(); k++) {
        if (u[j] % curr[k] == 0) {
          flag = false;
          break;
        }
      }
      if (flag) {
        ok = false;
        break;
      }
    }
    if (ok) {
      ans = (ans + b[0][i]) % mod;
    }
  }
  printf("%d\n", ans);
  return 0;
}
