#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
int a, b, c, d, i, j, m, k;
long long n;
char str[101];
bool one[101];
vector<int> cur[101], num[101];
vector<int> tot;
int mas[126][126], ans[126][126], tmp[126][126], tr[126][126];
map<vector<int>, int> q;
vector<int> cv[1001];
vector<int> now;
void rec(int v) {
  if (v >= (int)((tot).size())) {
    q[now] = k++;
    cv[k - 1] = now;
    return;
  }
  for (int _n((tot[v]) - 1), i(0); i <= _n; i++) {
    now.push_back(i);
    rec(v + 1);
    now.pop_back();
  }
}
inline void mul(int a[][126], int b[][126]) {
  for (int _n((k)-1), i(0); i <= _n; i++)
    for (int _n((k)-1), j(0); j <= _n; j++) tr[i][j] = b[j][i];
  for (int _n((k)-1), i(0); i <= _n; i++) {
    for (int _n((k)-1), j(0); j <= _n; j++) {
      long long t = 0;
      for (int _n((k)-1), z(0); z <= _n; z++) t += a[i][z] * tr[j][z];
      tmp[i][j] = t % 12345;
    }
  }
  for (int _n((k)-1), i(0); i <= _n; i++)
    for (int _n((k)-1), j(0); j <= _n; j++) a[i][j] = tmp[i][j];
}
int main() {
  scanf("%I64d%d", &n, &m);
  for (int _n((m)-1), i(0); i <= _n; i++) {
    scanf("%s%d", str, &a);
    if (a == 1)
      one[str[0] - 'A'] = 1;
    else
      cur[str[0] - 'A'].push_back(a);
  }
  for (int _n((26) - 1), i(0); i <= _n; i++) {
    if (one[i])
      ++c;
    else {
      for (int _n(((int)((cur[i]).size())) - 1), j(0); j <= _n; j++) {
        tot.push_back(cur[i][j]);
        num[i].push_back((int)tot.size() - 1);
      }
    }
  }
  rec(0);
  for (int _n((k)-1), i(0); i <= _n; i++) {
    for (int _n((26) - 1), j(0); j <= _n; j++) {
      if (one[j]) {
        ++mas[i][i];
      } else if ((int)((num[j]).size())) {
        vector<int> cur = cv[i];
        for (int _n(((int)((num[j]).size())) - 1), z(0); z <= _n; z++)
          cur[num[j][z]] = (cur[num[j][z]] + 1) % tot[num[j][z]];
        mas[i][q[cur]] = 1;
      }
    }
  }
  for (int _n((k)-1), i(0); i <= _n; i++) ans[i][i] = 1;
  while (n) {
    if (n % 2) mul(ans, mas);
    mul(mas, mas);
    n /= 2;
  }
  int res = 0;
  for (int _n((k)-1), i(0); i <= _n; i++) {
    vector<int> cur = cv[i];
    bool good = 1;
    for (int _n((26) - 1), j(0); j <= _n; j++) {
      if (one[j] || !(int)((num[j]).size())) continue;
      bool ok = 0;
      for (int _n(((int)((num[j]).size())) - 1), z(0); z <= _n; z++) {
        if (!cur[num[j][z]]) {
          ok = 1;
          break;
        }
      }
      if (!ok) {
        good = 0;
        break;
      }
    }
    if (good) res += ans[0][i];
  }
  printf("%d\n", res % 12345);
}
