#include <bits/stdc++.h>
using namespace std;
namespace fio {
streambuf* in = cin.rdbuf();
char bb[1000000], *s = bb, *t = bb;
inline long long read() {
  long long x = 0;
  char ch =
      (s == t && (t = (s = bb) + in->sgetn(bb, 1000000), s == t) ? EOF : *s++);
  while (ch < 48)
    ch = (s == t && (t = (s = bb) + in->sgetn(bb, 1000000), s == t) ? EOF
                                                                    : *s++);
  while (ch >= 48)
    x = x * 10 + ch - 48,
    ch = (s == t && (t = (s = bb) + in->sgetn(bb, 1000000), s == t) ? EOF
                                                                    : *s++);
  return x;
}
}  // namespace fio
using fio::read;
long long n;
int m, llm;
int lim[26];
vector<int> road[26];
map<array<int, 26>, int> huaji;
array<int, 26> pm;
class mat {
 public:
  int val[125][125];
  int* operator[](int x) { return val[x]; }
  mat operator*(mat _) {
    mat ans;
    for (int i = 1; i <= llm; i++)
      for (int u = 1; u <= llm; u++) {
        ans[i][u] = 0;
        for (int j = 1; j <= llm; j++)
          ans[i][u] = (ans[i][u] + val[i][j] * _[j][u]) % 12345;
      }
    return ans;
  }
};
mat ksm(mat x, long long y) {
  mat ans = x;
  y--;
  for (; y; y >>= 1, x = x * x)
    if (y & 1) ans = ans * x;
  return ans;
}
mat base;
int ans;
int main() {
  n = read(), m = read();
  if (!n) return cout << 1, 0;
  if (!m) return cout << 0, 0;
  for (int i = 1, x, y; i <= m; i++)
    x = read() + '0' - 'A', road[x].emplace_back(y = read()),
    lim[x] = max(lim[x], 1) * road[x].back();
  while (pm[25] < max(lim[25], 1)) {
    huaji[pm] = ++llm, pm[0]++;
    for (int i = 0; i < 25; i++)
      if (lim[i])
        pm[i + 1] += pm[i] / lim[i], pm[i] %= lim[i];
      else
        pm[i + 1] += pm[i], pm[i] = 0;
  }
  for (pair<array<int, 26>, int> it : huaji)
    for (int i = 0; i < 26; i++)
      if (lim[i])
        it.first[i] = (it.first[i] + 1) % lim[i],
        base[it.second][huaji[it.first]]++,
        it.first[i] = (it.first[i] - 1 + lim[i]) % lim[i];
  base = ksm(base, n);
  for (pair<array<int, 26>, int> it : huaji) {
    bool flag = 1;
    for (int i = 0, fx = 0; flag && i < 26; i++, flag &= fx, fx = 0)
      if (!lim[i])
        fx = 1;
      else
        for (int p : road[i]) fx |= !(it.first[i] % p);
    flag ? ans = (ans + base[1][it.second]) % 12345 : ans;
  }
  cout << ans << endl;
}
