#include <bits/stdc++.h>
using namespace std;
typedef int matrix[140][140];
const int modp = 12345;
int k, N, mod[30], base[30], cnt[30], num[30][30];
int legal[140], ans;
long long n;
matrix a, b;
void mul(matrix a, matrix b) {
  matrix c;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) c[i][j] = 0;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
        c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % modp;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) a[i][j] = c[i][j];
}
int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
int main() {
  cin >> n >> k;
  for (int i = 0; i < 26; i++) mod[i] = 1;
  for (int i = 1; i <= k; i++) {
    char type[4];
    int p, x;
    scanf("%s", type);
    p = type[0] - 'A';
    scanf("%d", &x);
    mod[p] *= x / gcd(x, mod[p]);
    cnt[p]++;
    num[p][cnt[p]] = x;
  }
  base[0] = 1;
  for (int i = 0; i < 26; i++) base[i + 1] = base[i] * mod[i];
  N = base[26];
  for (int i = 0; i < N; i++) {
    legal[i] = 1;
    for (int j = 0; j < 26; j++)
      if (cnt[j]) {
        int res = 0, zt;
        zt = i + base[j];
        if ((i / base[j] + 1) % mod[j] == 0) zt -= base[j + 1];
        b[i][zt]++;
        for (int k = 1; k <= cnt[j]; k++)
          if ((i / base[j]) % num[j][k] == 0) res = 1;
        legal[i] &= res;
      }
  }
  a[0][0] = 1;
  for (; n; n >>= 1) {
    if (n & 1) mul(a, b);
    mul(b, b);
  }
  for (int i = 0; i < N; i++)
    if (legal[i]) ans = (ans + a[0][i]) % modp;
  cout << ans << endl;
}
