#include <bits/stdc++.h>
using namespace std;
const int mod = 12345;
long long n;
int m, ans = 0;
int maxn[30];
vector<int> ok[30];
struct Matrix {
  int a[125][125];
  Matrix() { memset(a, 0, sizeof(a)); };
  Matrix operator*(const Matrix &x) const {
    Matrix ans = Matrix();
    for (int i = 1; i <= 123; i++)
      for (int j = 1; j <= 123; j++) {
        for (int k = 1; k <= 123; k++)
          ans.a[i][j] += a[i][k] * x.a[k][j] % mod, ans.a[i][j] %= mod;
      }
    return ans;
  }
  Matrix operator^(const long long &x) const {
    Matrix ans = (*this), temp = (*this);
    long long now = x;
    while (now) {
      if (now & 1) ans = ans * temp;
      temp = temp * temp;
      now >>= 1;
    }
    return ans;
  }
} mat;
struct dat {
  int val[30];
  bool operator<(const dat &a) const {
    for (int i = 1; i <= 26; i++) {
      if (val[i] == a.val[i]) continue;
      return val[i] < a.val[i];
    }
    return false;
  }
} chuzhi;
map<dat, int> mp;
int pcnt = 0;
void dfs(int pos, dat now) {
  if (pos == 27) {
    mp[now] = ++pcnt;
    return;
  }
  if (maxn[pos] == 0) dfs(pos + 1, now);
  for (int i = 0; i < maxn[pos]; i++) {
    now.val[pos] = i;
    dfs(pos + 1, now);
  }
}
void calc(int pos, dat now) {
  if (pos == 27) {
    ans += mat.a[1][mp[now]];
    ans %= mod;
    return;
  }
  if (maxn[pos] == 0) calc(pos + 1, now);
  for (int i = 0; i < maxn[pos]; i++) {
    bool flag = false;
    for (int j = 0; j < ok[pos].size(); j++)
      if (i % ok[pos][j] == 0) {
        flag = true;
        break;
      }
    if (flag) {
      now.val[pos] = i;
      calc(pos + 1, now);
    }
  }
}
char A;
int x, c;
int main() {
  scanf("%lld%d", &n, &m);
  if (n == 0) {
    printf("1\n");
    return 0;
  }
  if (m == 0) {
    printf("0\n");
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    scanf(" %c %d", &A, &x);
    c = A - 'A' + 1;
    if (maxn[c] == 0)
      maxn[c] = x;
    else
      maxn[c] *= x;
    ok[c].push_back(x);
  }
  dfs(1, chuzhi);
  for (map<dat, int>::iterator i = mp.begin(); i != mp.end(); i++) {
    int s = i->second;
    dat now = i->first;
    for (int j = 1; j <= 26; j++) {
      if (maxn[j] == 0) continue;
      dat temp = now;
      temp.val[j] = (temp.val[j] + 1) % maxn[j];
      mat.a[s][mp[temp]]++;
    }
  }
  mat = mat ^ ((long long)n - 1);
  calc(1, chuzhi);
  printf("%d\n", ans);
  return 0;
}
