#include <bits/stdc++.h>
using namespace std;
int total, cnt, f[66][205][205], answer[205], news[205], sum[1050], mul[1050];
char dif[205], ch[1050];
bool great[1050], can[1050][205];
vector<int> doing;
map<vector<int>, int> number;
int Rand() { return (rand() << 15) | rand(); }
void DFS(int current) {
  int i, size;
  bool solved;
  if (current > total) {
    number[doing] = ++cnt;
    size = doing.size();
    solved = true;
    for (i = 0; i < size; i++)
      if (!can[dif[i + 1]][doing[i]]) {
        solved = false;
        break;
      }
    if (solved) {
      great[cnt] = true;
    }
    return;
  }
  for (i = 0; i < sum[dif[current]]; i++) {
    doing.push_back(i);
    DFS(current + 1);
    doing.pop_back();
  }
  return;
}
int main() {
  int all, i, j, k, times, Log, result, current, next, size, temp;
  long long n;
  vector<int> vec;
  map<vector<int>, int>::iterator it, it2;
  srand((unsigned)time(0));
  for (i = 'A'; i <= 'Z'; i++) {
    sum[i] = 1;
  }
  scanf("%I64d%d\n", &n, &all);
  if (n == 0 && all == 0) {
    printf("1\n");
    return 0;
  }
  if (n == 0) {
    printf("1\n");
    return 0;
  }
  total = 0;
  for (i = 1; i <= all; i++) {
    scanf("%c%d\n", &ch[i], &mul[i]);
    sum[ch[i]] *= mul[i];
    dif[++total] = ch[i];
  }
  sort(dif + 1, dif + total + 1);
  for (i = j = 1; i < total; i++)
    if (dif[i + 1] != dif[j]) {
      dif[++j] = dif[i + 1];
    }
  total = j;
  for (i = 1; i <= all; i++) {
    for (j = 0; j < sum[ch[i]]; j += mul[i]) {
      can[ch[i]][j] = true;
    }
  }
  doing.clear();
  cnt = 0;
  DFS(1);
  for (it = number.begin(); it != number.end(); it++) {
    current = it->second;
    vec = it->first;
    size = vec.size();
    for (i = 0; i < size; i++) {
      temp = vec[i];
      vec[i] = (vec[i] + 1) % sum[dif[i + 1]];
      it2 = number.find(vec);
      next = it2->second;
      f[0][current][next]++;
      vec[i] = temp;
    }
  }
  Log = (int)(log2(n));
  for (times = 1; times <= Log; times++) {
    for (i = 1; i <= cnt; i++) {
      for (j = 1; j <= cnt; j++) {
        for (k = 1; k <= cnt; k++) {
          f[times][i][j] += f[times - 1][i][k] * f[times - 1][k][j];
          f[times][i][j] %= 12345;
        }
      }
    }
  }
  answer[1] = 1;
  for (times = Log; times >= 0; times--)
    if ((1ll << times) <= n) {
      n -= 1ll << times;
      memset(news, 0, sizeof(news));
      for (i = 1; i <= cnt; i++) {
        for (j = 1; j <= cnt; j++) {
          news[i] += f[times][i][j] * answer[j];
          news[i] %= 12345;
        }
      }
      memcpy(answer, news, sizeof(answer));
    }
  result = 0;
  for (i = 1; i <= cnt; i++)
    if (great[i]) {
      result += answer[i];
      result %= 12345;
    }
  printf("%d\n", result);
  return 0;
}
