#include <bits/stdc++.h>
using namespace std;
const int N = 200200, TO = 200200, LG = 100;
const unsigned long long INF = 2e18;
int m, L, cnt, x, y, z, u, s[TO][4], f[TO][4], fa[TO], l[TO], c[N], t[TO];
unsigned long long n, ans, a[LG + 2][4][4], X[4][4], Y[4][4];
char S[N];
void ins(int c) {
  x = y;
  l[y = ++cnt] = l[x] + 1;
  for (; x && s[x][c] == 0; x = fa[x]) s[x][c] = y;
  if (!x) {
    fa[y] = 1;
    return;
  }
  z = s[x][c];
  if (l[x] + 1 == l[z]) {
    fa[y] = z;
    return;
  } else {
    l[u = ++cnt] = l[x] + 1;
    fa[u] = fa[z], fa[z] = fa[y] = u;
    for (int i = 0; i <= 3; i++) s[u][i] = s[z][i];
    for (; x && s[x][c] == z; x = fa[x]) s[x][c] = u;
  }
}
void wrk() {
  for (int i = 1; i <= cnt; i++) c[l[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = 1; i <= cnt; i++) t[c[l[i]]--] = i;
  for (int i = cnt; i >= 1; i--) {
    x = t[i];
    for (int i = 0; i <= 3; i++) f[x][i] = N;
    for (int i = 0; i <= 3; i++) {
      if (!s[x][i])
        f[x][i] = 0;
      else
        for (int j = 0; j <= 3; j++) f[x][j] = min(f[x][j], f[s[x][i]][j] + 1);
    }
  }
}
void mul(unsigned long long A[4][4], unsigned long long B[4][4],
         unsigned long long C[4][4]) {
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) C[i][j] = INF;
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++)
      for (int k = 0; k <= 3; k++)
        C[i][j] = (C[i][j] < A[i][k] + B[k][j] ? C[i][j] : A[i][k] + B[k][j]);
}
void cha(unsigned long long A[4][4], unsigned long long B[4][4]) {
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) A[i][j] = B[i][j];
}
bool ok(unsigned long long A[4][4]) {
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++)
      if (A[i][j] + 1 <= n) return 1;
  return 0;
}
int main() {
  scanf("%lld", &n);
  scanf("%s", S + 1);
  m = strlen(S + 1);
  y = cnt = 1;
  for (int i = 1; i <= m; i++) ins(S[i] - 'A');
  wrk();
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) a[0][i][j] = f[s[1][j]][i] + 1;
  for (int i = 1; i <= LG; i++) {
    mul(a[i - 1], a[i - 1], a[i]);
    if (!ok(a[i])) {
      L = i;
      break;
    }
  }
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) X[i][j] = i == j ? 0 : INF;
  for (int i = L; i >= 0; i--) {
    mul(X, a[i], Y);
    if (ok(Y)) cha(X, Y), ans += (1ll << i);
  }
  printf("%lld\n", ans + 1);
}
