#include <bits/stdc++.h>
using namespace std;
const int N(2e5 + 21);
const long long INF(1LL << 61);
struct hh {
  int val;
  hh *par, *son[4];
} pool[N], *tail = pool, *rot, *last;
struct mat {
  long long a[4][4];
  mat() { memset(a, 0, sizeof a); }
  inline void initI() {
    for (int i(0); i < 4; i++) a[i][i] = INF;
  }
  inline mat operator*(const mat &b) {
    mat c;
    for (int i(0); i < 4; i++)
      for (int j(0); j < 4; j++) {
        c.a[i][j] = INF;
        for (int k(0); k < 4; k++)
          c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
      }
    return c;
  }
} c;
long long len;
int n;
char s[N];
inline hh *newnode(int v) {
  hh *x = tail++;
  x->val = v;
  return x;
}
inline mat pw(mat x, long long k) {
  mat res;
  res.initI();
  for (; k; k >>= 1) {
    if (k & 1) res = res * x;
    x = x * x;
  }
  return res;
}
inline void insert(int x) {
  hh *p = last, *np = newnode(p->val + 1);
  for (; p && !p->son[x]; p = p->par) p->son[x] = np;
  if (!p)
    np->par = rot;
  else {
    hh *q = p->son[x];
    if (q->val == p->val + 1)
      np->par = q;
    else {
      hh *nq = newnode(p->val + 1);
      memcpy(nq->son, q->son, sizeof q->son);
      nq->par = q->par;
      q->par = np->par = nq;
      for (; p && p->son[x] == q; p = p->par) p->son[x] = nq;
    }
  }
  last = np;
}
inline bool judge(long long k) {
  mat t = c;
  t = pw(t, k);
  long long mn = INF;
  for (int i(0); i < 4; i++)
    for (int j(0); j < 4; j++) mn = min(mn, t.a[i][j]);
  return mn < len;
}
int main() {
  cin >> len;
  scanf("%s", s + 1);
  n = strlen(s + 1);
  last = rot = tail++;
  for (int i(1); i <= n; i++) insert(s[i] - 'A');
  for (int i(0); i < 4; i++)
    for (int j(0); j < 4; j++) c.a[i][j] = INF;
  for (int e(0); e < 4; e++) {
    int l = 0;
    hh *cur = rot;
    for (int i(1); i <= n; i++) {
      for (; i + l <= n && cur->son[e]; cur = cur->son[s[i + l] - 'A'], l++)
        ;
      if (!cur->son[e])
        c.a[s[i] - 'A'][e] = min(c.a[s[i] - 'A'][e], (long long)l);
      if (l > 0) {
        l--;
        if (cur->par->val >= l) cur = cur->par;
      }
    }
  }
  long long l = 1, r = len, ans;
  while (l <= r) {
    long long mid(l + r >> 1);
    if (judge(mid - 1))
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  cout << ans << endl;
  return 0;
}
