#include <bits/stdc++.h>
using namespace std;
const int mod = 12345;
const int MAXN = 200 + 10;
vector<int> vec, v;
map<vector<int>, int> mp;
int t[50], cnt = 0, m;
bool mark[50][MAXN];
long long mat[MAXN][MAXN], mat2[MAXN][MAXN];
void f(long long n) {
  if (n == 1) return;
  f(n / 2);
  long long temp[MAXN][MAXN];
  for (int i = 0; i < cnt; i++)
    for (int j = 0; j < cnt; j++) {
      temp[i][j] = 0;
      for (int k = 0; k < cnt; k++)
        temp[i][j] = (temp[i][j] + mat[i][k] * mat[k][j]) % mod;
    }
  for (int i = 0; i < cnt; i++)
    for (int j = 0; j < cnt; j++) mat[i][j] = temp[i][j];
  if (n % 2 == 1) {
    for (int i = 0; i < cnt; i++)
      for (int j = 0; j < cnt; j++) {
        temp[i][j] = 0;
        for (int k = 0; k < cnt; k++)
          temp[i][j] = (temp[i][j] + mat[i][k] * mat2[k][j]) % mod;
      }
    for (int i = 0; i < cnt; i++)
      for (int j = 0; j < cnt; j++) mat[i][j] = temp[i][j];
  }
}
void make(int ind) {
  if (ind == m) {
    mp[v] = cnt++;
    return;
  }
  for (int i = 0; i < t[vec[ind]]; i++) {
    v[ind] = i;
    make(ind + 1);
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  ;
  long long n, c;
  cin >> n >> c;
  for (int i = 0; i < c; i++) {
    char a;
    int b;
    cin >> a >> b;
    if (t[a - 'A'] == 0) {
      t[a - 'A'] = b;
      vec.push_back(a - 'A');
      mark[a - 'A'][0] = true;
    } else
      t[a - 'A'] *= b;
    mark[a - 'A'][b] = true;
  }
  m = (int)vec.size();
  if (n == 0) {
    cout << 1 << endl;
    return 0;
  } else if (n == 1) {
    int o = 0;
    for (int i = 0; i < m; i++)
      if (mark[vec[i]][1]) o++;
    cout << o << endl;
    return o;
  }
  for (int i = 0; i < m; i++) v.push_back(0);
  make(0);
  for (auto u : mp)
    for (int i = 0; i < (int)u.first.size(); i++) {
      vector<int> x = u.first;
      x[i] = (x[i] + 1) % t[vec[i]];
      mat[u.second][mp[x]]++;
    }
  for (int i = 0; i < cnt; i++)
    for (int j = 0; j < cnt; j++) mat2[i][j] = mat[i][j];
  f(n);
  long long ans = 0;
  for (auto u : mp) {
    bool chck = true;
    for (int i = 0; i < (int)u.first.size(); i++) {
      bool ch = false;
      for (int k = 1; k < 200; k++)
        if (mark[vec[i]][k] && u.first[i] % k == 0) ch = true;
      chck = chck & ch;
    }
    if (chck) ans = (ans + mat[0][u.second]) % mod;
  }
  cout << ans << endl;
  return 0;
}
