#include <bits/stdc++.h>
using namespace std;
const long long inf = 3000000000000000000;
long long ans, n, mn;
int f[200005][4], ch[200005][4], pr[200005], ma[200005], d[200005], cnt, last,
    m;
char S[100005];
void add(int p, int c) {
  int np = last = ++cnt, q, nq;
  ma[np] = ma[p] + 1;
  while (p && !ch[p][c]) ch[p][c] = np, p = pr[p];
  if (!p)
    pr[np] = 1;
  else {
    q = ch[p][c];
    if (ma[p] + 1 == ma[q])
      pr[np] = q;
    else {
      nq = ++cnt;
      ma[nq] = ma[p] + 1;
      pr[nq] = pr[q];
      pr[q] = pr[np] = nq;
      memcpy(ch[nq], ch[q], sizeof ch[q]);
      while (ch[p][c] == q) ch[p][c] = nq, p = pr[p];
    }
  }
}
bool cmp(int a, int b) { return ma[a] < ma[b]; }
struct O {
  long long a[4][4];
} A[80], B, C, D;
O operator*(const O &A, const O &B) {
  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.a[i][k] + B.a[k][j]);
    }
  return C;
}
int main() {
  scanf("%lld%s", &n, S + 1);
  m = strlen(S + 1);
  cnt = last = 1;
  for (int i = 1; i <= m; ++i) add(last, S[i] - 'A');
  for (int i = 1; i <= cnt; ++i) d[i] = i;
  sort(d + 1, d + cnt + 1, cmp);
  for (int i = cnt; i; --i)
    for (int o = 0; o < 4; ++o) {
      if (!ch[d[i]][o]) {
        f[d[i]][o] = 1;
        continue;
      }
      f[d[i]][o] = 10000000;
      for (int c = 0; c < 4; ++c)
        if (ch[d[i]][c]) f[d[i]][o] = min(f[d[i]][o], f[ch[d[i]][c]][o] + 1);
    }
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) A[0].a[i][j] = f[ch[1][i]][j];
  for (int I = 1; I < 63; ++I) A[I] = A[I - 1] * A[I - 1];
  for (int I = 62; ~I; --I) {
    D = B * A[I];
    mn = inf;
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j) mn = min(mn, D.a[i][j]);
    if (mn < n) B = D, ans ^= 1ll << I;
  }
  printf("%lld\n", ans + 1);
  return 0;
}
