#include <bits/stdc++.h>
using namespace std;
const int MOD = 12345;
int add(int a, int b) { return a + b - (a + b >= MOD) * MOD; }
int mult(int a, int b) { return (1LL * a * b) % MOD; }
vector<vector<int> > make(int a, int b) {
  return vector<vector<int> >(a, vector<int>(b));
}
vector<vector<int> > mult(vector<vector<int> > a, vector<vector<int> > b) {
  vector<vector<int> > res = make(a.size(), b[0].size());
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b[0].size(); j++) {
      for (int k = 0; k < a[0].size(); k++) {
        res[i][j] = add(res[i][j], mult(a[i][k], b[k][j]));
      }
    }
  }
  return res;
}
vector<vector<int> > modpow(vector<vector<int> > x, long long p) {
  vector<vector<int> > ans = make(x.size(), x.size());
  for (int i = 0; i < x.size(); i++) ans[i][i] = 1;
  while (p) {
    if (p & 1) ans = mult(ans, x);
    p >>= 1;
    x = mult(x, x);
  }
  return ans;
}
long long n, m;
set<int> conditions[27];
int lcmd[27];
int good[27][130];
int D = 0;
map<vector<int>, int> mp;
vector<int> states[125];
void getstates(vector<int> v, int cur) {
  if (cur == 26) {
    states[D] = v;
    mp[v] = D;
    D++;
    return;
  }
  for (int i = 0; i < lcmd[cur]; i++) {
    v[cur] = i;
    getstates(v, cur + 1);
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    char c;
    int x;
    cin >> c >> x;
    conditions[c - 'A'].insert(x);
  }
  for (int i = 0; i < 26; i++) lcmd[i] = 1;
  for (int i = 0; i < 26; i++)
    for (auto t : conditions[i]) lcmd[i] *= t;
  for (int i = 0; i < 26; i++) {
    good[i][0] = 1;
    for (auto t : conditions[i]) {
      int cur = t;
      for (int j = 0; j < lcmd[i]; j += cur) {
        good[i][j] = 1;
      }
    }
  }
  vector<int> v(26);
  iota(v.begin(), v.end(), 0);
  getstates(v, 0);
  vector<vector<int> > A = make(D, D);
  for (int i = 0; i < D; i++) {
    vector<int> v = states[i];
    for (int j = 0; j < 26; j++)
      if (!conditions[j].empty()) {
        int c = lcmd[j];
        v[j] = (v[j] + 1) % c;
        A[i][mp[v]]++;
        v[j] = (v[j] - 1 + c) % c;
      }
  }
  A = modpow(A, n);
  int ans = 0;
  for (int i = 0; i < D; i++) {
    vector<int> v = states[i];
    bool flag = true;
    for (int j = 0; j < 26; j++)
      if (!good[j][v[j]]) flag = false;
    if (flag) {
      ans = add(ans, A[0][i]);
    }
  }
  cout << ans << endl;
  return 0;
}
