#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
struct Martix {
  long long a[4][4];
  void init() { memset(a, 0x3f, sizeof(a)); }
} Q;
Martix operator*(Martix A, Martix B) {
  Martix C;
  C.init();
  for (long long i = 0; i <= 3; i++) {
    for (long long j = 0; j <= 3; j++) {
      for (long long k = 0; k <= 3; k++) {
        C.a[i][j] = min(C.a[i][j], A.a[i][k] + B.a[k][j]);
      }
    }
  }
  return C;
}
Martix ksm(Martix A, long long b) {
  b--;
  Martix res;
  res = A;
  while (b) {
    if (b & 1) res = res * A;
    A = A * A;
    b >>= 1;
  }
  return res;
}
long long n, m, ch[1000005][4], dep[1000005], tot = 1;
char T[1000005];
void insert(long long x) {
  long long now = 1;
  for (long long i = 1; i <= min((m - x + 1), 10ll); i++) {
    long long c = T[x + i - 1] - 'A';
    if (!ch[now][c]) ch[now][c] = ++tot;
    dep[ch[now][c]] = dep[now] + 1;
    now = ch[now][c];
  }
  return;
}
void query(long long x) {
  long long now = 1;
  for (long long i = 1; i <= min((m - x + 1), 10ll); i++) {
    long long c = T[x + i - 1] - 'A';
    now = ch[now][c];
    for (long long j = 0; j <= 3; j++) {
      if (!ch[now][j]) Q.a[T[x] - 'A'][j] = min(Q.a[T[x] - 'A'][j], dep[now]);
    }
  }
}
long long check(long long x) {
  Martix G = ksm(Q, x);
  long long res = 1e18;
  for (long long i = 0; i <= 3; i++)
    for (long long j = 0; j <= 3; j++) res = min(res, G.a[i][j]);
  return (res < n);
}
signed main() {
  Q.init();
  n = read();
  if (n == 1) {
    puts("1");
    return 0;
  }
  scanf("%s", (T + 1));
  m = strlen(T + 1);
  for (long long i = 1; i <= m; i++) insert(i);
  for (long long i = 1; i <= m; i++) query(i);
  long long l = 1, r = n, mid, ans;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (check(mid))
      l = mid + 1, ans = mid;
    else
      r = mid - 1;
  }
  cout << ans + 1 << endl;
  return 0;
}
