#include <bits/stdc++.h>
using namespace std;
struct node {
  long long v[30];
  bool operator<(const node& rhs) const {
    for (int i = 1; i <= 26; i++) {
      if (v[i] == rhs.v[i]) continue;
      return v[i] < rhs.v[i];
    }
    return 0;
  }
} prepare;
struct edge {
  int r, c;
  long long jz[150][150];
  edge operator*(const edge& rhs) const {
    edge ans;
    ans.r = r, ans.c = rhs.c;
    for (register int i = 0; i <= ans.r; i++)
      for (register int j = 0; j <= ans.c; j++) ans.jz[i][j] = 0;
    for (register int i = 1; i <= r; i++)
      for (register int j = 1; j <= rhs.c; j++)
        for (register int k = 1; k <= c; k++)
          ans.jz[i][j] =
              (ans.jz[i][j] + jz[i][k] * rhs.jz[k][j] % 12345) % 12345;
    return ans;
  }
} A;
vector<int> G[1005];
map<node, int> m;
int c, maxn[1005], cnt;
long long n, ans;
void dfs(int Index, node x) {
  if (Index == 27) {
    m[x] = ++cnt;
    return;
  }
  if (!maxn[Index]) dfs(Index + 1, x);
  for (int i = 0; i < maxn[Index]; i++) {
    x.v[Index] = i;
    dfs(Index + 1, x);
  }
}
void Solve(int Index, node x) {
  if (Index == 27) {
    ans = (ans + A.jz[1][m[x]]) % 12345;
    return;
  }
  if (!maxn[Index]) Solve(Index + 1, x);
  for (int i = 0; i < maxn[Index]; i++) {
    bool flag = 0;
    for (int j = 0; j < G[Index].size(); j++) {
      if (i % G[Index][j] == 0) {
        flag = 1;
        break;
      }
    }
    if (flag) {
      x.v[Index] = i;
      Solve(Index + 1, x);
    }
  }
}
inline edge qkpow(edge x, long long y) {
  edge ans;
  ans.r = ans.c = x.r;
  for (register int i = 1; i <= ans.r; i++)
    for (register int j = 1; j <= ans.c; j++)
      if (i != j)
        ans.jz[i][j] = 0;
      else
        ans.jz[i][j] = 1;
  while (y) {
    if (y & 1) ans = ans * x;
    x = x * x;
    y >>= 1;
  }
  return ans;
}
int main() {
  scanf("%lld %d", &n, &c);
  if (!n) {
    printf("1\n");
    return 0;
  }
  if (!c) {
    printf("0\n");
    return 0;
  }
  bool vis[150] = {};
  for (int i = 1; i <= c; i++) {
    char a;
    int b;
    scanf("%s %d", &a, &b);
    if (!b) vis[a - 'A' + 1] = 1;
    if (!maxn[a - 'A' + 1]) {
      maxn[a - 'A' + 1] = b;
    } else {
      maxn[a - 'A' + 1] *= b;
    }
    G[a - 'A' + 1].push_back(b);
  }
  for (int i = 1; i <= 26; i++)
    if (vis[i]) maxn[i] = 0;
  dfs(1, prepare);
  for (map<node, int>::iterator i = m.begin(); i != m.end(); i++) {
    int Second = i->second;
    node First = i->first;
    for (int j = 1; j <= 26; j++) {
      if (maxn[j]) {
        node tmp = First;
        tmp.v[j] = (tmp.v[j] + 1) % maxn[j];
        A.jz[Second][m[tmp]]++;
      }
    }
  }
  A.r = A.c = 123;
  A = qkpow(A, n);
  Solve(1, prepare);
  printf("%lld\n", ans);
  return 0;
}
