#include <bits/stdc++.h>
using namespace std;
const int P = 12345;
int c, tot, val[26], a[26];
int64_t n;
vector<int> g[26];
vector<vector<int>> sta;
map<vector<int>, int> ID;
void dfs(int d) {
  if (d == 26) {
    auto u = vector<int>(a, a + 26);
    ID[u] = tot++;
    sta.push_back(u);
    return;
  }
  if (!val[d]) return dfs(d + 1);
  for (int t = 0; t < val[d]; ++t) {
    a[d] = t;
    dfs(d + 1);
  }
}
struct Mat {
  int v[125][125];
  Mat() { memset(v, 0, sizeof v); }
  Mat operator*(const Mat& b) const {
    Mat c;
    for (int k = 0; k < tot; ++k)
      for (int i = 0; i < tot; ++i)
        for (int j = 0; j < tot; ++j)
          c.v[i][j] = ((int64_t)v[i][k] * b.v[k][j] + c.v[i][j]) % P;
    return c;
  }
  Mat operator^(int64_t nn) {
    Mat b, a = *this;
    for (int i = 0; i < tot; ++i) b.v[i][i] = 1;
    while (nn) {
      if (nn & 1) b = b * a;
      nn >>= 1, a = a * a;
    }
    return b;
  }
} f;
int main() {
  scanf("%lld%d", &n, &c);
  while (c--) {
    char x;
    int y;
    scanf(" %c%d", &x, &y);
    g[x - 'A'].push_back(y);
  }
  for (int i = 0; i < 26; ++i)
    if (g[i].size()) {
      sort(g[i].begin(), g[i].end());
      vector<int> tmp;
      val[i] = 1;
      for (int x = 0; x < g[i].size(); ++x)
        if (g[i][x] != -1) {
          val[i] *= g[i][x];
          tmp.push_back(g[i][x]);
          for (int y = x + 1; y < g[i].size(); ++y) {
            if (g[i][y] % g[i][x] == 0) g[i][y] = -1;
          }
        }
      swap(g[i], tmp);
    }
  dfs(0);
  for (int d = 0; d < sta.size(); ++d) {
    for (int i = 0; i < 26; ++i)
      if (g[i].size()) {
        auto u = sta[d];
        u[i] = (u[i] + 1) % val[i];
        if (!ID.count(u)) throw;
        ++f.v[ID[u]][d];
      }
  }
  f = f ^ n;
  int ans = 0;
  auto chk = [&](int d, int w) {
    for (auto& t : g[d])
      if (w % t == 0) return 1;
    return 0;
  };
  for (int i = 0; i < tot; ++i) {
    auto u = sta[i];
    int ok = 1;
    for (int d = 0; d < 26; ++d)
      if (u[d]) {
        if (!chk(d, u[d])) ok = 0;
      }
    if (ok) ans = (ans + f.v[i][0]) % P;
  }
  printf("%d\n", ans);
}
