#include <bits/stdc++.h>
using namespace std;
typedef int Matrix[123][123];
void Print(Matrix &M, int N) {
  for (int i = 0; i < (N); i++) {
    for (int j = 0; j < (N); j++) printf("%lld ", M[i][j]);
    printf("\n");
  }
}
void Copy(Matrix &A, Matrix &B, int N) {
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (N); j++) A[i][j] = B[i][j];
}
void Clear(Matrix &M, int N) {
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (N); j++) M[i][j] = 0;
}
void One(Matrix &M, int N) {
  Clear(M, N);
  for (int i = 0; i < (N); i++) M[i][i] = 1;
}
void Mul(Matrix &A, Matrix &B, int N) {
  Matrix R;
  Clear(R, N);
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (N); j++)
      for (int k = 0; k < (N); k++)
        R[i][j] = (R[i][j] + A[i][k] * B[k][j]) % 12345;
  Copy(A, R, N);
}
void Pow(Matrix &M, int N, long long Pow) {
  Matrix R;
  Clear(R, N);
  for (int i = 0; i < (N); i++) R[i][i] = 1;
  while (Pow) {
    if (Pow & 1LL) Mul(R, M, N);
    Mul(M, M, N);
    Pow >>= 1LL;
  }
  Copy(M, R, N);
}
Matrix A;
int N;
vector<int> MulCrime[26];
long long C;
int Multiply[26];
int Index[26];
int Encode() {
  int val = 0;
  for (int i = 0; i < (26); i++) val = val * Multiply[i] + Index[i];
  return val;
}
void Decode(int val) {
  for (int i = (26) - 1; i >= 0; i--) {
    Index[i] = val % Multiply[i];
    val /= Multiply[i];
  }
}
bool OkCrime(int c) {
  if (MulCrime[c].empty()) return true;
  for (int i = 0; i < (int(MulCrime[c].size())); i++)
    if (Index[c] % MulCrime[c][i] == 0) return true;
  return false;
}
bool OkTotal(int k) {
  Decode(k);
  for (int i = 0; i < (26); i++)
    if (!OkCrime(i)) return false;
  return true;
}
void Inc(int &a, int m) { a = (a + 1) % m; }
void Dec(int &a, int m) { a = (a + m - 1) % m; }
int main() {
  int Size = 1;
  cin >> C >> N;
  for (int i = 0; i < (26); i++) Multiply[i] = 1;
  for (int i = 0; i < (N); i++) {
    string s;
    int m;
    cin >> s >> m;
    int index = s[0] - 'A';
    MulCrime[index].push_back(m);
    Size *= m;
    Multiply[index] *= m;
  }
  for (int i = 0; i < (Size); i++) {
    Decode(i);
    for (int j = 0; j < (26); j++)
      if (!MulCrime[j].empty()) {
        Inc(Index[j], Multiply[j]);
        Inc(A[Encode()][i], 12345);
        Dec(Index[j], Multiply[j]);
      }
  }
  Pow(A, Size, C);
  int Res = 0;
  for (int i = 0; i < (Size); i++) {
    if (OkTotal(i)) {
      Res = (Res + A[i][0]) % 12345;
    }
  }
  printf("%d\n", Res);
  return 0;
}
