#include <bits/stdc++.h>
using namespace std;
const int N = 128;
const int C = 1024;
vector<int> b[26];
int prod[26];
int p[26];
void decode(int code, int a[26]) {
  for (int i = (0); i < (26); ++i) {
    a[i] = code % prod[i];
    code /= prod[i];
  }
}
int encode(int a[26]) {
  int code = 0;
  for (int i = 25; i >= 0; --i) code = code * prod[i] + a[i];
  return code;
}
const int mod = 12345;
int d[N][N];
int m;
void mult(int a[N][N], int b[N][N], int c[N][N]) {
  memset(d, 0, sizeof(d));
  for (int k = (0); k < (m); ++k)
    for (int i = (0); i < (m); ++i)
      for (int j = (0); j < (m); ++j) {
        d[i][j] += a[i][k] * b[k][j];
        d[i][j] %= mod;
      }
  memcpy(c, d, sizeof(d));
}
int a[N][N], res[N][N];
int main() {
  long long n;
  int c;
  cin >> n >> c;
  for (int i = (0); i < (c); ++i) {
    char ch;
    int x;
    cin >> ch >> x;
    b[ch - 'A'].push_back(x);
  }
  m = 1;
  for (int i = (0); i < (26); ++i) {
    prod[i] = 1;
    for (int j = (0); j < (((int)(b[i]).size())); ++j) {
      m *= b[i][j];
      prod[i] *= b[i][j];
    }
  }
  for (int i = (0); i < (m); ++i)
    for (int j = (0); j < (26); ++j)
      if (((int)(b[j]).size())) {
        decode(i, p);
        p[j]++;
        p[j] %= prod[j];
        int code = encode(p);
        a[i][code]++;
      }
  for (int i = (0); i < (m); ++i) res[i][i] = 1;
  while (n) {
    if (n & 1) mult(res, a, res);
    mult(a, a, a);
    n /= 2;
  }
  int ans = 0;
  for (int i = (0); i < (m); ++i) {
    decode(i, p);
    bool bad = false;
    for (int j = (0); j < (26); ++j)
      if (((int)(b[j]).size())) {
        bool ok = false;
        for (int k = (0); k < (((int)(b[j]).size())); ++k)
          if (p[j] % b[j][k] == 0) {
            ok = true;
            break;
          }
        if (!ok) {
          bad = true;
          break;
        }
      }
    if (!bad) {
      ans += res[0][i];
      ans %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}
