#include <bits/stdc++.h>
using namespace std;
long long C, N;
int MaxN;
struct Mat {
  long long a[130][130];
};
void Mul(const Mat &a, const Mat &b, Mat &c, int size) {
  for (int i = 0; i < size; ++i) {
    for (int j = 0; j < size; ++j) {
      c.a[i][j] = 0;
      for (int k = 0; k < size; ++k) c.a[i][j] += a.a[i][k] * b.a[k][j];
      c.a[i][j] %= 12345;
    }
  }
}
void Pow(const Mat &a, Mat &b, long long n, int size) {
  int t[80], index = 0;
  while (n) t[index++] = n & 1, n >>= 1;
  Mat m;
  memset(m.a, 0, sizeof(m.a));
  for (int i = 0; i < size; ++i) m.a[i][i] = 1;
  Mat ret = m;
  for (int i = index - 1; i >= 0; --i) {
    Mul(m, m, ret, size);
    memcpy(m.a, ret.a, sizeof(m.a));
    if (t[i]) {
      Mul(m, a, ret, size);
      memcpy(m.a, ret.a, sizeof(m.a));
    }
  }
  b = ret;
}
int gcd(int x, int y) {
  while (x && y) {
    if (x >= y)
      x %= y;
    else
      y %= x;
  }
  return x + y;
}
int main() {
  cin >> N >> C;
  vector<int> itv[26];
  int f[26] = {};
  for (int i = 0; i < C; ++i) {
    char x;
    int t;
    cin >> x >> t;
    itv[x - 'A'].push_back(t);
  }
  MaxN = 1;
  for (int i = 0; i < 26; ++i) {
    if (itv[i].size() == 0) continue;
    unique(itv[i].begin(), itv[i].end());
    f[i] = 1;
    for (int j = 0; j < itv[i].size(); ++j)
      f[i] = f[i] / gcd(f[i], itv[i][j]) * itv[i][j];
    MaxN *= f[i];
  }
  Mat init, ret;
  memset(init.a, 0, sizeof(init.a));
  int t[26] = {};
  for (int i = 0; i < MaxN; ++i) {
    int cur = i;
    for (int j = 0; j < 26; ++j) {
      if (f[j] == 0) continue;
      t[j] = cur % f[j];
      cur /= f[j];
    }
    for (int j = 0; j < 26; ++j) {
      if (f[j] == 0) continue;
      t[j]++;
      if (t[j] >= f[j]) t[j] -= f[j];
      int val = 0;
      for (int k = 25; k >= 0; --k) {
        if (f[k] == 0) continue;
        val = val * f[k] + t[k];
      }
      init.a[i][val]++;
      t[j]--;
      if (t[j] < 0) t[j] = f[j] - 1;
    }
  }
  Pow(init, ret, N, MaxN);
  int ans = 0;
  for (int i = 0; i < MaxN; ++i) {
    bool ac = 1;
    int cur = i;
    for (int j = 0; j < 26; ++j) {
      if (f[j] == 0) continue;
      t[j] = cur % f[j];
      cur /= f[j];
    }
    for (int j = 0; j < 26; ++j) {
      if (f[j] == 0) continue;
      int flag = 0;
      for (int k = 0; k < itv[j].size(); ++k)
        if (t[j] % itv[j][k] == 0) flag = 1;
      if (flag == 0) {
        ac = 0;
        break;
      }
    }
    if (ac) ans = (ans + ret.a[i][0]) % 12345;
  }
  printf("%d\n", ans);
  return 0;
}
