#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:60000000")
using namespace std;
template <class T>
T sqr(T x) {
  return x * x;
}
double const pi = 3.1415926535897932384626433832795;
int const inf = (int)1e9 + 1;
long long const inf64 = (long long)4e18 + 1;
const string name = "d";
const int NMAX = 128;
const int P = 12345;
long long n;
int m, K, k[256], zn[NMAX], used[NMAX];
char ch[NMAX];
vector<int> sdfjh[NMAX];
vector<pair<char, int> > value[NMAX];
map<vector<pair<char, int> >, int> num;
int res[NMAX][NMAX], a[NMAX][NMAX];
long long q[NMAX][NMAX];
int gcd(int a, int b) {
  if (a * b == 0)
    return a + b;
  else
    return gcd(b % a, a);
}
vector<pair<char, int> > now;
void rec(int x) {
  if (x == 256) {
    num[now] = K;
    value[K] = now;
    K++;
    return;
  }
  if (!used[x])
    rec(x + 1);
  else {
    for (int i = 0; i < (int)k[x]; i++) {
      now.push_back(make_pair((char)x, i));
      rec(x + 1);
      now.pop_back();
    }
  }
}
int main() {
  for (int i = 0; i < (int)256; i++) {
    used[i] = 0;
    k[i] = 1;
  }
  cin >> n >> m;
  if (n == 0) {
    cout << 1 << endl;
    return 0;
  }
  if (m == 0) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 0; i < (int)m; i++) {
    scanf(" %c%d", &ch[i], &zn[i]);
    sdfjh[ch[i]].push_back(zn[i]);
    k[ch[i]] = k[ch[i]] * zn[i] / gcd(k[ch[i]], zn[i]);
    used[ch[i]] = 1;
  }
  K = 0;
  now.clear();
  rec(0);
  m = value[0].size();
  memset(a, 0, sizeof(a));
  for (int i = 0; i < (int)K; i++)
    for (int j = 0; j < (int)m; j++) {
      vector<pair<char, int> > tmp = value[i];
      tmp[j].second = (tmp[j].second + 1) % k[tmp[j].first];
      a[i][num[tmp]]++;
    }
  memset(res, 0, sizeof(res));
  for (int i = 0; i < (int)K; i++) res[i][i] = 1;
  while (n > 0) {
    if (n & 1) {
      memset(q, 0, sizeof(q));
      for (int i = 0; i < (int)K; i++)
        for (int j = 0; j < (int)K; j++)
          for (int f = 0; f < (int)K; f++) q[i][j] += res[i][f] * a[f][j];
      for (int i = 0; i < (int)K; i++)
        for (int j = 0; j < (int)K; j++) res[i][j] = q[i][j] % P;
    }
    memset(q, 0, sizeof(q));
    for (int i = 0; i < (int)K; i++)
      for (int j = 0; j < (int)K; j++)
        for (int f = 0; f < (int)K; f++) q[i][j] += a[i][f] * a[f][j];
    for (int i = 0; i < (int)K; i++)
      for (int j = 0; j < (int)K; j++) a[i][j] = q[i][j] % P;
    n >>= 1;
  }
  int ans = 0;
  for (int i = 0; i < (int)K; i++) {
    int ok = 1;
    for (int j = 0; j < (int)m; j++) {
      int tmp = 0;
      char c = value[0][j].first;
      for (int f = 0; f < (int)sdfjh[c].size(); f++)
        if (value[i][j].second % sdfjh[c][f] == 0) tmp = 1;
      ok &= tmp;
    }
    ans = (ans + ok * res[0][i]) % P;
  }
  cout << ans << endl;
  return 0;
}
