#include <bits/stdc++.h>
using namespace std;
template <typename T>
void Out(T res) {
  cout << res << endl;
  exit(0);
}
long long n;
vector<int> T[26], all;
pair<int, int> pos[26];
int Add(int a, int b, int mod) {
  a += b;
  if (a >= mod) return a - mod;
  if (a < 0) return a + mod;
  return a;
}
int Mul(int a, int b, int mod) { return (a * b) % mod; }
vector<int> decode(int state) {
  vector<int> res;
  for (int i = (0), _b((int)(all).size()); i < _b; ++i) {
    res.push_back(state % all[i]);
    state /= all[i];
  }
  return res;
}
int code(vector<int> res) {
  int state = 0, p = 1;
  for (int i = (0), _b((int)(all).size()); i < _b; ++i) {
    state += res[i] * p;
    p *= all[i];
  }
  return state;
}
const int N = 124;
const int MOD = 12345;
int a[N][N], res[N][N];
void mul(int a[][N], int b[][N], int c[][N]) {
  int res[N][N];
  memset(res, 0, sizeof(res));
  for (int i = (0), _b(N); i < _b; ++i)
    for (int j = (0), _b(N); j < _b; ++j)
      for (int k = (0), _b(N); k < _b; ++k)
        res[i][j] = Add(res[i][j], Mul(a[i][k], b[k][j], MOD), MOD);
  for (int i = (0), _b(N); i < _b; ++i)
    for (int j = (0), _b(N); j < _b; ++j) c[i][j] = res[i][j];
}
int main() {
  int m;
  cin >> n >> m;
  int ones = 0;
  for (int i = (0), _b(m); i < _b; ++i) {
    string s;
    int t;
    cin >> s >> t;
    T[s[0] - 'A'].push_back(t);
  }
  for (int i = (0), _b(26); i < _b; ++i) {
    sort(T[i].begin(), T[i].end());
    T[i].erase(unique(T[i].begin(), T[i].end()), T[i].end());
  }
  int len = 0, prev = 0;
  for (int i = (0), _b(26); i < _b; ++i) {
    len = 0;
    for (int j = (0), _b((int)(T[i]).size()); j < _b; ++j) {
      if (T[i][j] == 1) {
        ones++;
        break;
      }
      len++;
      all.push_back(T[i][j]);
    }
    pos[i] = pair<int, int>(prev, prev + len);
    prev += len;
  }
  for (int i = (0), _b(N); i < _b; ++i) {
    a[i][i] = ones;
    vector<int> curr = decode(i);
    for (int j = (0), _b(26); j < _b; ++j) {
      if (!(pos[j].second - pos[j].first)) continue;
      for (int p = (pos[j].first), _b(pos[j].second); p < _b; ++p) {
        curr[p] = Add(curr[p], +1, all[p]);
      }
      a[i][code(curr)]++;
      for (int p = (pos[j].first), _b(pos[j].second); p < _b; ++p) {
        curr[p] = Add(curr[p], -1, all[p]);
      }
    }
  }
  for (int i = (0), _b(N); i < _b; ++i) res[i][i] = 1;
  for (; n; n >>= 1) {
    if (n & 1) mul(res, a, res);
    mul(a, a, a);
  }
  int ans = 0;
  for (int i = (0), _b(N); i < _b; ++i) {
    vector<int> curr = decode(i);
    int k = 1;
    for (int j = (0), _b(26); j < _b; ++j) {
      if (!(pos[j].second - pos[j].first)) continue;
      k = 0;
      for (int p = (pos[j].first), _b(pos[j].second); p < _b; ++p)
        if (curr[p] == 0) {
          k = 1;
          break;
        }
      if (!k) break;
    }
    ans = Add(ans, k * res[0][i], MOD);
  }
  cout << ans << endl;
  return 0;
}
