#include <bits/stdc++.h>
using namespace std;
inline void hello() { freopen("ha.in", "r", stdin); }
char t[100005];
int n, node, tr[3000005][4], f[3000005][4];
unsigned long long L, A[4][4], B[4][4], C[4][4], M[4][4];
inline void mul() {
  memcpy(C, A, sizeof C);
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, j = 0; j < _r; ++j) A[i][j] = 1e18;
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, k = 0; k < _r; ++k)
      for (int _r = 4, j = 0; j < _r; ++j)
        A[i][j] = min(A[i][j], C[i][k] + C[k][j]);
}
inline void prod() {
  memcpy(C, B, sizeof C);
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, j = 0; j < _r; ++j) B[i][j] = 1e18;
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, k = 0; k < _r; ++k)
      for (int _r = 4, j = 0; j < _r; ++j)
        B[i][j] = min(B[i][j], A[i][k] + C[k][j]);
}
inline unsigned long long calc(unsigned long long second) {
  --second;
  memcpy(A, M, sizeof A);
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, j = 0; j < _r; ++j)
      if (i == j)
        B[i][j] = 0;
      else
        B[i][j] = 1e18;
  for (; second; second >>= 1, mul())
    if (second & 1) prod();
  unsigned long long an = 1e18;
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, j = 0; j < _r; ++j) an = min(an, B[i][j]);
  return an + 1;
}
void dfs(int u) {
  for (int _r = 4, i = 0; i < _r; ++i)
    if (tr[u][i]) dfs(tr[u][i]);
  for (int _r = 4, i = 0; i < _r; ++i) {
    if (!tr[u][i])
      f[u][i] = 1;
    else {
      f[u][i] = 1000000;
      for (int _r = 4, j = 0; j < _r; ++j)
        if (tr[u][j]) f[u][i] = min(f[u][i], f[tr[u][j]][i] + 1);
    }
  }
}
int main() {
  scanf("%I64u", &L);
  scanf("%s", t + 1);
  n = strlen(t + 1);
  node = 1;
  for (int _r = n, i = 1; i <= _r; ++i) {
    int j = 0, u = 1;
    for (; j < 30 && i + j <= n; ++j) {
      int &v = tr[u][t[i + j] - 'A'];
      if (!v) v = ++node;
      u = v;
    }
  }
  dfs(1);
  for (int _r = 4, i = 0; i < _r; ++i)
    for (int _r = 4, j = 0; j < _r; ++j) M[i][j] = f[tr[1][i]][j];
  unsigned long long l = 0, r = L + 1;
  for (; l + 1 < r;) {
    unsigned long long m = l + r >> 1;
    if (calc(m) <= L)
      l = m;
    else
      r = m;
  }
  printf("%I64u\n", l);
}
