#include <bits/stdc++.h>
using namespace std;
const int MOD = 12345;
const int MAXN = 1100;
int maxv[30];
vector<int> G[30], ans;
long long m;
int n, cntv;
struct Matrix {
  long long map[125][125];
  Matrix operator*(const Matrix &b) const {
    Matrix c;
    memset(c.map, 0, sizeof(c.map));
    for (int i = 1; i <= cntv; ++i)
      for (int j = 1; j <= cntv; ++j)
        for (int k = 1; k <= cntv; ++k)
          c.map[i][j] = (c.map[i][j] + map[i][k] * b.map[k][j]) % MOD;
    return c;
  }
} M, rnt;
struct Node {
  int a[30];
  bool operator<(const Node &b) const {
    for (int i = 1; i <= 26; ++i)
      if (a[i] != b.a[i]) return a[i] < b.a[i];
    return 0;
  }
} t;
map<Node, int> hsh;
bool Check(Node t) {
  for (int i = 1; i <= 26; ++i) {
    if (maxv[i] == 0) continue;
    bool flag = false;
    for (int j = 0; j < G[i].size(); ++j)
      if (t.a[i] % G[i][j] == 0) {
        flag = true;
        break;
      }
    if (!flag) return false;
  }
  return true;
}
void DFS(int u) {
  if (u == 27) {
    hsh[t] = ++cntv;
    if (Check(t)) ans.push_back(cntv);
    return;
  }
  if (maxv[u] == 0)
    t.a[u] = 0, DFS(u + 1);
  else {
    for (int i = 0; i < maxv[u]; ++i) t.a[u] = i, DFS(u + 1);
  }
}
void Pow(long long k) {
  for (int i = 1; i <= cntv; ++i) rnt.map[i][i] = 1;
  while (k) {
    if (k & 1) rnt = rnt * M;
    M = M * M;
    k >>= 1;
  }
}
int main() {
  scanf("%lld%d", &m, &n);
  char c;
  int x;
  for (int i = 1; i <= n; ++i) {
    scanf(" %c%d", &c, &x);
    G[c - 'A' + 1].push_back(x);
    if (maxv[c - 'A' + 1])
      maxv[c - 'A' + 1] *= x;
    else
      maxv[c - 'A' + 1] = x;
  }
  if (m == 0) {
    printf("1");
    return 0;
  }
  if (n == 0) {
    printf("0");
    return 0;
  }
  Node cur, nxt;
  int v1, v2;
  DFS(1);
  for (map<Node, int>::iterator i = hsh.begin(); i != hsh.end(); ++i) {
    cur = i->first;
    v1 = i->second;
    for (int j = 1; j <= 26; ++j) {
      if (maxv[j] == 0) continue;
      nxt = cur;
      nxt.a[j] = (nxt.a[j] + 1) % maxv[j];
      v2 = hsh[nxt];
      M.map[v2][v1]++;
    }
  }
  Pow(m);
  int sumv = 0;
  for (int i = 0; i < ans.size(); ++i) sumv = (sumv + rnt.map[ans[i]][1]) % MOD;
  printf("%d\n", sumv);
  return 0;
}
