#include <bits/stdc++.h>
const int mod = 12345;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
inline void up(int &a, int b) {
  if ((a += b) >= mod) a -= mod;
}
inline long long pw(long long base, long long p) {
  base %= mod;
  long long res = 1;
  for (; p; p >>= 1, base = base * base % mod)
    if (p & 1) res = res * base % mod;
  return res;
}
int __sz = 1;
struct matrix {
  int s[150][150];
  inline matrix() { __builtin_memset(s, 0, sizeof s); }
  inline friend matrix operator*(const matrix &lhs, const matrix &rhs) {
    matrix res;
    for (register int i = 0; i < __sz; i++) {
      for (register int j = 0; j < __sz; j++) {
        long long tmp = 0;
        for (register int k = 0; k < __sz; k++)
          tmp += static_cast<long long>(lhs.s[i][k]) * rhs.s[k][j];
        res.s[i][j] = tmp % mod;
      }
    }
    return res;
  }
} BASE, RES;
long long n;
int m;
int mp[300], ret[300], __name, prod[300];
int base[300];
std::vector<int> v[300];
inline int get(int x, int i) { return x / base[i - 1] % prod[i]; }
inline bool check(int x) {
  for (int i = 1; i <= __name; i++) {
    bool find = false;
    int now = get(x, i);
    for (std::vector<int>::iterator it = v[i].begin(); it != v[i].end(); it++)
      if (now % *it == 0) {
        find = true;
        break;
      }
    if (!find) return false;
  }
  return true;
}
int main() {
  scanf("%lld%d", &n, &m);
  for (int i = 1, x, ch; i <= m; i++) {
    char __ch;
    scanf("%1s%d", &__ch, &x);
    ch = static_cast<int>(__ch);
    if (!mp[ch]) mp[ch] = ++__name, ret[__name] = ch, prod[__name] = 1;
    prod[mp[ch]] *= x;
    v[mp[ch]].push_back(x);
    __sz *= x;
  }
  base[0] = 1;
  for (int i = 1; i <= __name; i++) base[i] = base[i - 1] * prod[i];
  for (int i = 0; i < __sz; i++) {
    for (int j = 1; j <= __name; j++) {
      int now = get(i, j), nxt = (now + 1) % prod[j];
      up(BASE.s[i][i + (nxt - now) * base[j - 1]], 1);
    }
  }
  RES.s[0][0] = 1;
  for (; n; n >>= 1, BASE = BASE * BASE)
    if (n & 1) RES = RES * BASE;
  int ans = 0;
  for (int i = 0; i < __sz; i++)
    if (check(i)) up(ans, RES.s[0][i]);
  printf("%d\n", ans);
  return 0;
}
