#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
long long read() {
  long long x = 0;
  long long f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -f;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
  return x;
}
long long maxn[30];
vector<long long> G[30];
struct matrix {
  long long s[305][305];
  void inti() {
    memset(s, 0, sizeof(s));
    return;
  }
  void One() {
    inti();
    for (int i = 1; i <= 123; i++) s[i][i] = 1;
    return;
  }
  matrix operator*(matrix b) const {
    matrix f;
    f.inti();
    for (int i = 1; i <= 123; i++)
      for (int j = 1; j <= 123; j++)
        for (int k = 1; k <= 123; k++)
          f.s[i][j] = (f.s[i][j] + s[i][k] * b.s[k][j] % 12345) % 12345;
    return f;
  }
} mat, ret;
struct node {
  long long val[30];
  bool operator<(node b) const {
    for (int i = 1; i <= 26; i++) {
      if (val[i] == b.val[i]) continue;
      return val[i] < b.val[i];
    }
    return 0;
  }
} st;
long long cnt;
map<node, long long> a;
void dfs(long long p, node now) {
  if (p == 27) {
    a[now] = ++cnt;
    return;
  }
  if (!maxn[p]) dfs(p + 1, now);
  for (int i = 0; i < maxn[p]; i++) {
    now.val[p] = i;
    dfs(p + 1, now);
  }
}
long long ans;
void calc(long long p, node now) {
  if (p == 27) {
    ans = (ans + ret.s[1][a[now]]) % 12345;
    return;
  }
  if (!maxn[p]) calc(p + 1, now);
  for (int i = 0; i < maxn[p]; i++) {
    bool f = 0;
    for (int j = 0; j < G[p].size(); j++)
      if (i % G[p][j] == 0) {
        f = 1;
        break;
      }
    if (f) {
      now.val[p] = i;
      calc(p + 1, now);
    }
  }
}
long long n = read(), m = read();
bool vis[30];
int main() {
  if (n == 0) {
    puts("1");
    return 0;
  }
  if (m == 0) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    char A;
    long long x;
    scanf(" %c %lld", &A, &x);
    long long c = A - 'A' + 1;
    if (x == 0) {
      vis[c] = 1;
    }
    if (!maxn[c])
      maxn[c] = x;
    else
      maxn[c] *= x;
    G[c].push_back(x);
  }
  for (int i = 1; i <= 26; i++)
    if (vis[i]) maxn[i] = 0;
  dfs(1, st);
  for (map<node, long long>::iterator it = a.begin(); it != a.end(); it++) {
    node pt = it->first;
    long long s = it->second;
    for (int j = 1; j <= 26; j++) {
      if (!maxn[j]) continue;
      node tp = pt;
      tp.val[j] = (tp.val[j] + 1) % maxn[j];
      mat.s[s][a[tp]]++;
    }
  }
  ret.One();
  n;
  while (n) {
    if (n & 1) ret = ret * mat;
    n >>= 1;
    mat = mat * mat;
  }
  calc(1, st);
  printf("%lld", ans);
}
