#include <bits/stdc++.h>
using namespace std;
const int maxn = 126, MOD = 12345;
int res[maxn][maxn], tmp[maxn][maxn], POW[maxn][maxn], flag[maxn], check[maxn];
int A[maxn][maxn], B[maxn][maxn], a[maxn << 3], b[maxn << 3];
int m, size = 1, temp, ans, vec[maxn << 3], judge;
char ch;
long long n;
void mul(int a[maxn][maxn], int b[maxn][maxn], int c[maxn][maxn]) {
  for (int i = 1; i <= size; i++)
    for (int j = 1; j <= size; j++) {
      tmp[i][j] = 0;
      for (int k = 1; k <= size; k++)
        tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;
    }
  for (int i = 1; i <= size; i++)
    for (int j = 1; j <= size; j++) c[i][j] = tmp[i][j];
}
void power(int a[maxn][maxn], long long p, int b[maxn][maxn]) {
  for (int i = 1; i <= size; i++)
    for (int j = 1; j <= size; j++) POW[i][j] = a[i][j], res[i][j] = (i == j);
  while (p) {
    if (p & 1) mul(res, POW, res);
    mul(POW, POW, POW);
    p >>= 1;
  }
  for (int i = 1; i <= size; i++)
    for (int j = 1; j <= size; j++) b[i][j] = res[i][j];
}
int main() {
  scanf("%lld%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("\n%c %d", &ch, &b[i]);
    a[i] = ch - 'A';
    flag[a[i]] = 1;
    size *= b[i];
  }
  for (int i = 0; i <= size - 1; i++) {
    temp = i;
    for (int j = m; j >= 1; j--) vec[j] = temp % b[j], temp /= b[j];
    for (int j = 0; j <= 25; j++)
      if (flag[j]) {
        temp = 0;
        for (int k = 1; k <= m; k++)
          temp = temp * b[k] + (vec[k] + (a[k] == j)) % b[k];
        A[temp + 1][i + 1]++;
      }
  }
  power(A, n, A);
  B[1][1] = 1;
  mul(A, B, B);
  for (int i = 0; i <= size - 1; i++) {
    temp = i;
    for (int j = m; j >= 1; j--) check[a[j]] |= !(temp % b[j]), temp /= b[j];
    judge = 1;
    for (int j = 0; j <= 25; j++) {
      judge &= !(flag[j] ^ check[j]);
      check[j] = 0;
    }
    if (judge) ans = (ans + B[i + 1][1]) % MOD;
  }
  printf("%d\n", ans);
  return 0;
}
