#include <bits/stdc++.h>
using namespace std;
const int MOD = 12345;
const int STD_SIZE = 130;
int msize;
struct Matrix {
  int mat[STD_SIZE][STD_SIZE];
  Matrix() { memset(mat, 0, sizeof mat); }
  inline Matrix operator*(const Matrix& b) {
    Matrix ret;
    for (int i = 0; i < msize; i++)
      for (int j = 0; j < msize; j++)
        for (int k = 0; k < msize; k++)
          ret.mat[i][j] = (ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % MOD;
    return ret;
  }
};
map<char, vector<int> > mp;
vector<int> vecs[26];
int lvl[30], prd[30];
int main() {
  long long N;
  int C;
  cin >> N >> C;
  for (int i = 1; i <= C; i++) {
    char buf[10];
    int k;
    scanf("%s%d", buf, &k);
    mp[buf[0]].push_back(k);
  }
  for (int chr = 0; chr < 26; chr++) {
    vector<int>& vec = mp[chr + 'A'];
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    lvl[chr] = 1;
    for (int i = 0; i < (int)vec.size(); i++) lvl[chr] *= vec[i];
  }
  prd[0] = 1;
  for (int i = 1; i <= 26; i++) prd[i] = prd[i - 1] * lvl[i - 1];
  msize = prd[26];
  Matrix trans;
  for (int s = 0; s < msize; s++) {
    for (int chr = 0; chr < 26; chr++) {
      if (mp[chr + 'A'].size() == 0) continue;
      int cur_bit = s / prd[chr] % lvl[chr];
      int nxt_bit = (cur_bit + 1) % lvl[chr];
      int nxt_s = s + (nxt_bit - cur_bit) * prd[chr];
      trans.mat[s][nxt_s]++;
    }
  }
  Matrix unit;
  for (int i = 0; i < msize; i++) unit.mat[i][i] = 1;
  while (N) {
    if (N & 1) unit = unit * trans;
    trans = trans * trans;
    N >>= 1;
  }
  int ans = 0;
  for (int i = 0; i < 26; i++) vecs[i] = mp[i + 'A'];
  for (int s = 0; s < msize; s++) {
    bool nvald = false;
    for (int chr = 0; chr < 26; chr++) {
      if (vecs[chr].size() == 0) continue;
      int cur_bit = s / prd[chr] % lvl[chr];
      bool flg = false;
      for (int i = 0; i < (int)vecs[chr].size(); i++)
        if (cur_bit % vecs[chr][i] == 0) {
          flg = true;
          break;
        }
      if (!flg) {
        nvald = true;
        break;
      }
    }
    if (!nvald) ans = (ans + unit.mat[0][s]) % MOD;
  }
  cout << ans % MOD << '\n';
}
