#include <bits/stdc++.h>
using namespace std;
const int mod = 12345;
const int N = 1000 + 5;
const int L = 123;
template <class T>
inline void getin(T& num) {
  char c;
  bool flag = 0;
  num = 0;
  while ((c = getchar()) < '0' || c > '9')
    if (c == '-') flag = 1;
  while (c >= '0' && c <= '9') {
    num = num * 10 + c - 48;
    c = getchar();
  }
  if (flag) num = -num;
}
long long n;
map<vector<int>, int> num;
vector<int> letter, let[L + 5], mo[30];
int m, x, d, cnt = 1, p[30], vis[30];
char str[2];
bool zero[30];
inline void add(long long& a, long long b) {
  a += b;
  if (a >= mod) a -= mod;
}
struct matrix {
  long long mat[L + 5][L + 5];
  inline void Init() { memset(mat, 0, sizeof mat); }
  inline void One() {
    memset(mat, 0, sizeof mat);
    for (int i = 1; i <= cnt; i++) mat[i][i] = 1;
  }
  matrix operator*(const matrix& a) const {
    matrix ret;
    ret.Init();
    for (int i = 1; i <= cnt; i++)
      for (int j = 1; j <= cnt; j++)
        for (int k = 1; k <= cnt; k++)
          add(ret.mat[i][j], mat[i][k] * a.mat[k][j] % mod);
    return ret;
  }
  matrix operator*=(const matrix& a) { return (*this) = (*this) * a; }
  matrix operator^(const long long b) const {
    matrix ret, tep;
    long long p = b;
    ret.One(), tep = (*this);
    while (p) {
      if (p & 1) ret *= tep;
      tep *= tep, p >>= 1;
    }
    return ret;
  }
  matrix operator^=(const long long b) { return (*this) = (*this) ^ b; }
} statu;
void dfs(int x) {
  if (x == 27) {
    num[letter] = ++cnt;
    for (int i = 0; i <= 26; i++) let[cnt].push_back(letter[i]);
    return;
  }
  if (!p[x]) return dfs(x + 1);
  for (int i = 0; i < p[x]; i++) letter[x] = i, dfs(x + 1);
}
void build(int x) {
  if (x == 27) {
    int id = num[letter];
    vector<int> tep;
    for (int i = 0; i <= 26; i++) tep.push_back(letter[i]);
    for (int i = 1; i <= 26; i++) {
      if (!p[i]) continue;
      int to = (tep[i] + 1) % p[i];
      swap(tep[i], to);
      add(statu.mat[id][num[tep]], 1);
      swap(tep[i], to);
    }
    return;
  }
  if (!p[x]) return build(x + 1);
  for (int i = 0; i < p[x]; i++) letter[x] = i, build(x + 1);
}
inline bool check(int p) {
  for (int i = 1; i <= 26; i++) {
    int siz = mo[i].size();
    if (!siz) {
      if (!let[p][i])
        continue;
      else
        return 0;
    }
    bool flag = 0;
    for (int j = 0; j < siz; j++) {
      if (!mo[i][j]) {
        if (!let[p][i]) {
          flag = 1;
          break;
        }
        continue;
      }
      if (let[p][i] % mo[i][j] == 0) {
        flag = 1;
        break;
      }
    }
    if (!flag) return 0;
  }
  return 1;
}
int main() {
  getin(n), getin(m);
  if (!n) puts("1"), exit(0);
  if (!m) puts("0"), exit(0);
  letter.push_back(0);
  for (int i = 1; i <= 26; i++) p[i] = 1, letter.push_back(0);
  for (int i = 1; i <= m; i++) {
    scanf("%s%d", str, &d);
    if (!d)
      zero[str[0] - 'A' + 1] = 1;
    else
      p[str[0] - 'A' + 1] *= d;
    mo[str[0] - 'A' + 1].push_back(d);
    vis[str[0] - 'A' + 1]++;
  }
  for (int i = 1; i <= 26; i++)
    if (zero[i] && vis[i] == 1) p[i] = 0;
  for (int i = 1; i <= 26; i++)
    if (!vis[i]) p[i] = 0;
  dfs(1);
  for (int i = 1; i <= 26; i++) letter[i] = 0;
  build(1);
  for (int i = 1; i <= 26; i++) letter[i] = 0;
  for (int i = 1; i <= 26; i++) {
    if (!p[i]) continue;
    letter[i] = 1 % p[i];
    if (num.count(letter)) add(statu.mat[1][num[letter]], 1);
    letter[i] = 0;
  }
  for (int i = 1; i <= 26; i++) letter[i] = 0;
  statu ^= n;
  long long ans = 0;
  for (int i = 2; i <= cnt; i++)
    if (check(i)) add(ans, statu.mat[1][i]);
  cout << ans << '\n';
  return 0;
}
