#include <bits/stdc++.h>
using namespace std;
struct aaa {
  long long num[4][4];
} b;
long long n, m, mx, cnt[4][4][15], v[2000010], ch[2000010][4], sz;
char s[1000010];
void ins(long long st) {
  long long i, op, now = 0, u = s[st] - 'A';
  for (i = st; i <= min(m, st + mx - 1); i++) {
    op = s[i] - 'A';
    if (!ch[now][op]) ch[now][op] = ++sz;
    now = ch[now][op];
    if (!v[now]) v[now] = 1, ++cnt[u][op][i - st + 1];
  }
}
aaa operator*(aaa a, aaa b) {
  aaa c;
  long long i, j, k;
  for (i = 0; i < 4; i++)
    for (j = 0; j < 4; j++) c.num[i][j] = n + 1;
  for (k = 0; k < 4; k++)
    for (i = 0; i < 4; i++)
      for (j = 0; j < 4; j++)
        c.num[i][j] = min(c.num[i][j], a.num[i][k] + b.num[k][j]);
  return c;
}
aaa ksm(aaa a, long long y) {
  y--;
  aaa xlh = a;
  while (y) {
    if (y & 1) xlh = xlh * a;
    a = a * a;
    y /= 2;
  }
  return xlh;
}
long long pd(long long x) {
  aaa xlh = ksm(b, x);
  long long i, j, flag = 0;
  for (i = 0; i < 4; i++)
    for (j = 0; j < 4; j++) flag |= (xlh.num[i][j] < n);
  return flag;
}
long long solve() {
  long long l = 1, r = n, mid, ans = 0;
  while (l < r) {
    mid = (l + r) / 2;
    if (pd(mid))
      ans = mid, l = mid + 1;
    else
      r = mid;
  }
  return l;
}
long long pw(long long x, long long y) {
  long long xlh = 1;
  while (y) {
    if (y & 1) xlh = xlh * x;
    x = x * x;
    y /= 2;
  }
  return xlh;
}
int main() {
  long long i, j, k;
  scanf("%lld", &n);
  scanf("%s", s + 1);
  m = strlen(s + 1);
  mx = min(11ll, m);
  for (i = 1; i <= m; i++) ins(i);
  for (i = 0; i < 4; i++)
    for (j = 0; j < 4; j++)
      for (k = mx; k >= 2; k--)
        if (cnt[i][j][k] != pw(4, k - 2)) b.num[i][j] = k - 1;
  printf("%lld", solve());
}
