#include <bits/stdc++.h>
using namespace std;
const int maxn = 12345;
long long n, w;
int now, m, i, j, k, root[130][130], temp[130][130], ans[130][130], len[26],
    t[26][111], stu, o;
char ch;
bool ok(int x) {
  int now = 1, i, j, o;
  for (i = 0; i < 26; i++)
    if (len[i] && t[i][0]) {
      bool flag = false;
      for (j = 1; j <= t[i][0]; j++)
        if (x / now % len[i] % t[i][j] == 0) {
          flag = true;
          break;
        }
      if (!flag) return false;
      now *= len[i];
    }
  return true;
}
void mul(int a[][130], int b[][130]) {
  memset(temp, 0, sizeof(temp));
  int i, j, o;
  for (i = 0; i < k; i++)
    for (o = 0; o < k; o++)
      if (a[i][o])
        for (j = 0; j < k; j++)
          (temp[i][j] += a[i][o] * b[o][j] % maxn) %= maxn;
  for (i = 0; i < k; i++)
    for (j = 0; j < k; j++) a[i][j] = temp[i][j];
}
int main() {
  cin >> n >> m;
  for (i = 0; i < 26; i++) len[i] = 1;
  for (i = 1; i <= m; i++) {
    cin >> ch;
    o = ch - 'A';
    cin >> t[o][++t[o][0]];
    for (j = 1; t[o][j] != t[o][t[o][0]] && j < t[o][0]; j++)
      ;
    if (j == t[o][0])
      len[o] *= t[o][t[o][0]];
    else
      t[o][0]--;
  }
  k = 1;
  for (i = 0; i < 26; i++)
    if (len[i]) k *= len[i];
  for (i = 0; i < k; i++) {
    now = 1;
    for (j = 0; j < 26; j++)
      if (len[j] && t[j][0]) {
        if (i / now % len[j] == len[j] - 1)
          stu = i - (len[j] - 1) * now;
        else
          stu = i + now;
        root[stu][i]++;
        now *= len[j];
      }
  }
  for (i = 0; i < k; i++) ans[i][i] = 1;
  while (n) {
    if (n & 1) mul(ans, root);
    n /= 2;
    mul(root, root);
  }
  for (i = 0; i < k; i++)
    if (ok(i)) (w += ans[i][0]) %= maxn;
  cout << w;
  return 0;
}
