#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
vector<vector<int> > add;
vector<int> our;
int a[123][123];
int res[123][123];
int mod = 12345;
vector<int> decode(int num) {
  vector<int> a;
  a.resize(our.size());
  for (int i = (0); i < (our.size()); ++i) {
    a[i] = num % our[i];
    num /= our[i];
  }
  return a;
}
int encode(vector<int> a) {
  int p = 1;
  int res = 0;
  for (int i = (0); i < (a.size()); ++i) {
    res += a[i] * p;
    p *= our[i];
  }
  return res;
}
void mul(int a[123][123], int b[123][123], int c[123][123]) {
  int d[123][123];
  memset(d, 0, sizeof(d));
  for (int i = (0); i < (123); ++i)
    for (int j = (0); j < (123); ++j)
      for (int k = (0); k < (123); ++k) {
        d[i][j] += a[i][k] * b[k][j];
        d[i][j] %= mod;
      }
  memcpy(c, d, sizeof(d));
}
int main() {
  long long n;
  int c, v;
  g.resize(26);
  cin >> n >> c;
  string s;
  if (n == 0) {
    cout << 1 << endl;
    return 0;
  }
  if (c == 0) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = (0); i < (c); ++i) {
    cin >> s >> v;
    g[s[0] - 'A'].push_back(v);
  }
  for (int i = (0); i < (26); ++i) {
    sort(g[i].begin(), g[i].end());
    g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
  }
  int cnt = 0;
  add.resize(26);
  for (int i = (0); i < (26); ++i)
    if (g[i].size()) {
      if (g[i][0] == 1)
        cnt++;
      else
        for (int j = (0); j < (g[i].size()); ++j) {
          our.push_back(g[i][j]);
          add[i].push_back(our.size() - 1);
        }
    }
  for (int i = (0); i < (123); ++i) {
    vector<int> b = decode(i);
    a[i][i] += cnt;
    for (int j = (0); j < (26); ++j)
      if (add[j].size()) {
        vector<int> c = b;
        for (int k = (0); k < (add[j].size()); ++k) {
          c[add[j][k]]++;
          c[add[j][k]] %= our[add[j][k]];
        }
        int v = encode(c);
        a[i][v]++;
      }
  }
  for (int i = (0); i < (123); ++i) res[i][i] = 1;
  while (n) {
    if (n & 1) mul(res, a, res);
    mul(a, a, a);
    n /= 2;
  }
  int ans = 0;
  for (int i = (0); i < (123); ++i) {
    vector<int> b = decode(i);
    bool f = true;
    for (int j = (0); j < (26); ++j) {
      if (add[j].size()) {
        bool f1 = false;
        for (int k = (0); k < (add[j].size()); ++k) {
          int v = add[j][k];
          if (b[v] == 0) f1 = true;
        }
        if (!f1) f = false;
      }
    }
    if (f) {
      ans += res[0][i];
      ans %= mod;
    }
  }
  cout << ans << endl;
}
