#include <bits/stdc++.h>
using namespace std;
const long long M = 1005, X = 143, MOD = 12345;
long long n, m, mul[M], t[32], cc, ansi, flag;
bool mark[X], mm[32][X];
char c[M];
vector<long long> v, w[X], z;
map<vector<long long>, long long> mapi;
struct matrix {
  long long a[X][X];
  matrix() {
    for (int i = 1; i <= 130; i++) {
      for (int j = 1; j <= 130; j++) {
        a[i][j] = 0;
      }
    }
  }
  matrix operator*(matrix b) {
    matrix c;
    for (int i = 1; i <= cc; i++) {
      for (int j = 1; j <= cc; j++) {
        for (int k = 1; k <= cc; k++) {
          c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
        }
      }
    }
    return c;
  }
};
matrix p, ans;
void make(long long x) {
  if (x > 25) {
    cc++;
    mapi[v] = cc;
    w[cc] = v;
    return;
  }
  if (!t[x]) {
    v.push_back(0);
    make(x + 1);
    v.pop_back();
    return;
  }
  for (int i = 0; i < t[x]; i++) {
    v.push_back(i);
    make(x + 1);
    v.pop_back();
  }
}
matrix pow(matrix x, long long r) {
  if (r == 1) return x;
  matrix y = pow(x, r / 2);
  y = y * y;
  if (r % 2) y = y * x;
  return y;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  if (!n) {
    cout << 1 << endl;
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    cin >> c[i] >> mul[i];
    if (t[c[i] - 'A']) {
      t[c[i] - 'A'] *= mul[i];
    } else {
      t[c[i] - 'A'] = mul[i];
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < t[c[i] - 'A']; j += mul[i]) {
      mm[c[i] - 'A'][j] = 1;
    }
  }
  make(0);
  for (int i = 1; i <= cc; i++) {
    flag = 1;
    for (int j = 0; j < 26; j++) {
      if (t[j] && !mm[j][w[i][j]]) {
        flag = 0;
        break;
      }
    }
    mark[i] = flag;
    for (int j = 0; j < 26; j++) {
      if (t[j]) {
        z = w[i];
        z[j] = (w[i][j] + 1) % t[j];
        p.a[i][mapi[z]]++;
      }
    }
  }
  ans = pow(p, n);
  for (int i = 1; i <= cc; i++) {
    if (mark[i]) {
      ansi = (ansi + ans.a[1][i]) % MOD;
    }
  }
  cout << ansi << endl;
  return 0;
}
