#include <bits/stdc++.h>
using namespace std;
struct Matrix {
  int arr[125][125], n;
  Matrix(int _n = 0) {
    n = _n;
    memset(arr, 0, sizeof(arr));
  }
  inline Matrix operator*(const Matrix &a) const {
    Matrix res(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++)
          res.arr[i][j] = (res.arr[i][j] + arr[i][k] * a.arr[k][j]) % 12345;
      }
    }
    return res;
  }
  inline Matrix operator*=(const Matrix &a) { return *this = *this * a; }
};
inline Matrix quick_pow(Matrix a, long long n) {
  Matrix res(a.n);
  res.arr[0][0] = 1;
  while (n) {
    if (n & 1) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}
int arr[35], coef[35];
vector<int> mul[35];
bool vis[35];
inline int gcd(int x, int y) {
  int r;
  while (y) {
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}
int main() {
  long long t;
  int n;
  scanf("%lld%d", &t, &n);
  for (int i = 0; i < 26; i++) arr[i] = 1;
  for (int i = 0; i < n; i++) {
    char c;
    int x;
    scanf("%*c%c%d", &c, &x);
    arr[c - 'A'] *= x;
    mul[c - 'A'].push_back(x);
    vis[c - 'A'] = true;
  }
  int cur = 1;
  for (int i = 0; i < 26; i++) {
    coef[i] = cur;
    cur *= arr[i];
  }
  Matrix mat(cur);
  for (int i = 0; i < cur; i++) {
    for (int j = 0; j < 26; j++) {
      if (!vis[j]) continue;
      int x = i / coef[j] % arr[j];
      mat.arr[i][i + ((x + 1) % arr[j] - x) * coef[j]]++;
    }
  }
  Matrix res = quick_pow(mat, t);
  int ans = 0;
  for (int i = 0; i < cur; i++) {
    bool g = true;
    for (int j = 0; j < 26 && g; j++) {
      if (!vis[j]) continue;
      int x = i / coef[j] % arr[j];
      bool f = false;
      for (auto y : mul[j]) {
        if (!(x % y)) f = true;
      }
      if (!f) g = false;
    }
    if (g) ans = (ans + res.arr[0][i]) % 12345;
  }
  printf("%d\n", ans);
  return 0;
}
