#include <bits/stdc++.h>
using namespace std;
const long long mod = 12345;
vector<vector<long long> > multiply(vector<vector<long long> >& a,
                                    vector<vector<long long> >& b) {
  int n = a.size();
  vector<vector<long long> > res(n, vector<long long>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        res[i][j] += (a[i][k] * b[k][j]) % mod;
        res[i][j] %= mod;
      }
    }
  }
  return res;
}
vector<vector<long long> > pwr(vector<vector<long long> > a, long long b) {
  if (b == 1) {
    return a;
  }
  vector<vector<long long> > half = pwr(a, (b >> 1));
  half = multiply(half, half);
  if (b & 1) {
    half = multiply(half, a);
  }
  return half;
}
const int crimes = 26;
vector<set<int> > laws(crimes);
vector<long long> prod(crimes, 0);
int from_state_to_num(vector<long long> com) {
  int ans = 0;
  for (int i = 0; i < crimes; i++) {
    if (prod[i]) {
      ans *= prod[i];
      ans += com[i];
    }
  }
  return ans;
}
vector<long long> from_num_to_state(int num) {
  vector<long long> ans(crimes, 0);
  for (int i = crimes - 1; i >= 0; i--) {
    if (prod[i]) {
      ans[i] = num % prod[i];
      num /= prod[i];
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  int c;
  cin >> n >> c;
  if (!n) {
    cout << 1 << "\n";
    return 0;
  }
  long long p = 1;
  for (int i = 0; i < c; i++) {
    char crime;
    int how_many;
    cin >> crime >> how_many;
    laws[crime - 'A'].insert(how_many);
    if (!prod[crime - 'A']) {
      prod[crime - 'A'] = 1;
    }
    prod[crime - 'A'] *= how_many;
    p *= how_many;
  }
  vector<vector<long long> > m(p, vector<long long>(p, 0));
  for (int i = 0; i < p; i++) {
    vector<long long> old = from_num_to_state(i);
    for (int j = 0; j < crimes; j++) {
      if (!prod[j]) {
        continue;
      }
      vector<long long> nw = old;
      nw[j] = (nw[j] + 1) % prod[j];
      m[i][from_state_to_num(nw)]++;
    }
  }
  m = pwr(m, n);
  long long ans = 0;
  for (int i = 0; i < p; i++) {
    vector<long long> old = from_num_to_state(i);
    bool good = true;
    for (int j = 0; j < crimes; j++) {
      if (laws[j].size()) {
        bool now = false;
        for (int k : laws[j]) {
          if (old[j] % k == 0) {
            now = true;
          }
        }
        good &= now;
      }
    }
    if (good) {
      ans += m[0][i];
      ans %= mod;
    }
  }
  cout << ans << "\n";
  return 0;
}
