#include <bits/stdc++.h>
using namespace std;
const long long maxn = 128, maxm = 3100, mod = 12345;
long long n, m, a[maxn][maxm], t, b[maxm], d[maxm], sum;
pair<char, long long> p[maxm];
char c;
bool mark[30], l, mark2[30];
struct matric {
  long long a[maxn][maxn];
  matric() { memset(a, 0, sizeof a); }
  void print() {
    cout << endl;
    for (int i = 0; i < 5; i++)
      for (int j = 0; j < 5; j++) cout << a[i][j];
    cout << endl;
  }
  matric operator*(const matric b) {
    matric c;
    for (int i = 0; i < maxn; i++)
      for (int j = 0; j < maxn; j++)
        for (int k = 0; k < maxn; k++) {
          c.a[i][j] += a[i][k] * b.a[k][j];
          c.a[i][j] %= mod;
        }
    return c;
  }
};
matric v, ans, f;
matric pow(matric a, long long n) {
  if (n == 1) return v;
  f = pow(a, n / 2);
  f = f * f;
  if (n % 2) f = f * v;
  return f;
}
void H(long long x, long long b[]) {
  if (x == m) {
    for (int i = 0; i < m; i++) a[t][i] = b[i];
    t++;
    return;
  }
  for (int i = 0; i < p[x].second; i++) {
    b[x] = i;
    H(x + 1, b);
    b[x] = 0;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    long long x;
    cin >> c >> x;
    p[i] = make_pair(c, x);
    mark[c - 'A'] = true;
  }
  if (!n) {
    cout << 1 << endl;
    return 0;
  }
  if (!m) {
    cout << 0 << endl;
    return 0;
  }
  sort(p, p + m);
  for (int i = 0; i < m; i++) d[i] = p[i].first - 'A';
  H(0, b);
  memset(b, 0, sizeof b);
  for (int i = 0; i < t; i++) {
    for (int j = 0; j < 26; j++) {
      if (!mark[j]) continue;
      for (int k = 0; k < m; k++) b[k] = a[i][k];
      for (int k = 0; k < m; k++)
        if (d[k] == j) b[k] = (b[k] + 1) % p[k].second;
      for (int k = 0; k < t; k++) {
        l = 1;
        for (int u = 0; u < m; u++)
          if (a[k][u] != b[u]) l = 0;
        if (l) v.a[i][k]++;
      }
    }
  }
  ans = pow(v, n);
  for (int j = 0; j < t; j++) {
    memset(mark2, 0, sizeof mark2);
    l = 1;
    for (int i = 0; i < m; i++)
      if (a[j][i] == 0) mark2[d[i]] = true;
    for (int i = 0; i < 26; i++)
      if (mark[i] && !mark2[i]) l = 0;
    if (l) {
      sum += ans.a[0][j];
      sum %= mod;
    }
  }
  cout << sum << endl;
  return 0;
}
