#include <bits/stdc++.h>
#pragma GCC optimaze("Ofast");
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int mod = 12345;
struct matrix {
  vector<vector<int>> ms;
  int n, m;
  matrix(int n, int m) {
    this->n = n, this->m = m;
    ms.resize(n);
    for (int i = 0; i < n; i++) ms[i].resize(m, 0);
  }
  matrix(int n) {
    this->n = n, this->m = n;
    ms.resize(n);
    for (int i = 0; i < n; i++) ms[i].resize(n, 0);
    for (int i = 0; i < n; i++) ms[i][i] = 1;
  }
  matrix(vector<int> &a) {
    this->n = a.size();
    this->m = 1;
    ms.resize(n);
    for (int i = 0; i < n; i++) ms[i].push_back(a[i]);
  }
};
matrix operator*(matrix &a, matrix &b) {
  matrix c(a.n, b.m);
  int d = a.m;
  for (int i = 0; i < a.n; i++)
    for (int j = 0; j < b.m; j++)
      for (int k = 0; k < d; k++)
        c.ms[i][j] = (c.ms[i][j] + a.ms[i][k] * b.ms[k][j]) % mod;
  return c;
}
void powmod(matrix &a, long long n) {
  matrix res(a.n);
  while (n)
    if (!(n % 2))
      a = (a * a), n /= 2;
    else
      res = (res * a), n--;
  a = res;
}
int nod(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
vector<int> res[30];
int res2[30];
vector<int> func(int x, vector<int> &b) {
  vector<int> op;
  for (int i = 0; i < b.size(); i++) {
    op.push_back(x % b[i]);
    x /= b[i];
  }
  return op;
}
int func2(vector<int> &op, vector<int> b) {
  int x = 0;
  for (int i = b.size() - 1; i >= 0; i--) {
    x *= b[i];
    x += op[i];
  }
  return x;
}
signed main() {
  srand(1);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.setf(ios::fixed);
  cout.precision(10);
  long long n, c;
  cin >> n >> c;
  for (int i = 0; i < c; i++) {
    char a;
    int b;
    cin >> a >> b;
    res[a - 'A'].push_back(b);
  }
  vector<int> wq, wq2;
  long long sz = 1;
  for (int i = 0; i < 30; i++) {
    if (res[i].size() != 0) {
      int x = res[i][0];
      for (int j = 0; j < res[i].size(); j++)
        x = x * res[i][j] / nod(x, res[i][j]);
      res2[i] = x;
      sz = sz * res2[i];
      wq.push_back(res2[i]);
      wq2.push_back(i);
    }
  }
  matrix mt(sz, sz);
  for (int i = 0; i < sz; i++) {
    vector<int> op = func(i, wq);
    for (int j = 0; j < op.size(); j++) {
      vector<int> op2 = op;
      op2[j] = (op2[j] - 1 + wq[j]) % wq[j];
      int x = func2(op2, wq);
      mt.ms[i][x]++;
    }
  }
  powmod(mt, n);
  vector<int> dp(sz);
  dp[0] = 1;
  matrix we(dp);
  we = mt * we;
  int ans = 0;
  for (int i = 0; i < sz; i++) {
    vector<int> op = func(i, wq);
    bool tr = true;
    for (int j = 0; j < op.size(); j++) {
      bool tr2 = false;
      for (int k = 0; k < res[wq2[j]].size(); k++) {
        if (op[j] % res[wq2[j]][k] == 0) tr2 = true;
      }
      tr = (tr & tr2);
    }
    if (tr) ans = (ans + we.ms[i][0]) % mod;
  }
  cout << ans;
}
