#include <bits/stdc++.h>
using namespace std;
const char lf = '\n';
template <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
template <typename T1, typename T2>
inline T1 gmax(T1 &a, T2 b) {
  return a = a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 gmin(T1 &a, T2 b) {
  return a = a < b ? a : b;
}
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline long long ty() {
  long long a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
template <typename T>
inline int ts(T *s) {
  int a = 0, c = fetch();
  while (c <= 32 && c != EOF) c = fetch();
  while (c > 32 && c != EOF) s[a++] = c, c = fetch();
  s[a] = 0;
  return a;
}
}  // namespace ae86
using ae86::ts;
using ae86::ty;
const int _ = 100007, alp = 4;
const long long linf = 0x3f3f3f3f3f3f3f3f;
struct martix {
  long long val[alp][alp];
  long long *operator[](int x) { return val[x]; }
  void be0() { memset(val, 63, sizeof(val)); }
  void be1() {
    memset(val, 63, sizeof(val));
    for (int i = 0; i < alp; i++) val[i][i] = 0;
  }
  friend martix operator*(martix a, martix b) {
    martix c;
    for (int i = 0; i < alp; i++)
      for (int j = 0; j < alp; j++)
        for (int k = 0; k < alp; k++) c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
    return c;
  }
  martix() { be0(); }
};
martix powa(martix a, long long t) {
  martix b;
  for (int i = 0; i < alp; i++) b[0][i] = 1;
  while (t) {
    if (t & 1) b = b * a;
    a = a * a, t >>= 1;
  }
  return b;
}
struct riki {
  static const int _t = _ << 1;
  int fa[_t], ch[_t][alp], len[_t], las, tcnt;
  void push(int c) {
    int p = las, np = ++tcnt;
    las = np;
    len[np] = len[p] + 1;
    while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
    if (!p) {
      fa[np] = 1;
      return;
    }
    int q = ch[p][c];
    if (len[q] == len[p] + 1) {
      fa[np] = q;
      return;
    }
    int nq = ++tcnt;
    len[nq] = len[p] + 1, memcpy(ch[nq], ch[q], sizeof(ch[q]));
    fa[nq] = fa[q], fa[q] = fa[np] = nq;
    while (p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
  }
  long long fx[_t];
  int ed[_t];
  long long dfs(int x) {
    if (ed[x]) return fx[x];
    for (int i = 0; i < alp; i++)
      if (ch[x][i]) fx[x] = min(fx[x], dfs(ch[x][i]) + 1);
    ed[x] = 1;
    return fx[x];
  }
  riki() {
    memset(fa, 0, sizeof(fa));
    memset(ch, 0, sizeof(ch));
    memset(len, 0, sizeof(len));
    memset(fx, 63, sizeof(fx));
    memset(ed, 0, sizeof(ed));
    las = tcnt = 1;
  }
} sa;
long long n;
int m, str[_];
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = ty(), m = ts(str + 1);
  for (int i = 1; i <= m; i++) str[i] -= 'A';
  for (int i = 1; i <= m; i++) sa.push(str[i]);
  martix tran;
  for (int i = 0; i < alp; i++) {
    memset(sa.fx, 63, sizeof(sa.fx));
    memset(sa.ed, 0, sizeof(sa.ed));
    for (int j = 1; j <= sa.tcnt; j++)
      if (!sa.ch[j][i]) sa.fx[j] = 1;
    for (int j = 0; j < alp; j++) tran[i][j] = sa.dfs(sa.ch[1][j]);
  }
  long long l = 0, r = n;
  while (r > l) {
    long long mid = (l + r + 1) >> 1;
    martix res = powa(tran, mid);
    int got = 0;
    for (int i = 0; i < alp; i++)
      if (res[0][i] <= n) {
        got = 1;
        break;
      }
    if (!got)
      r = mid - 1;
    else
      l = mid;
  }
  cout << l + 1 << lf;
  return 0;
}
