#include <bits/stdc++.h>
using namespace std;
long long dist[4][4];
int qnt[4][4];
char str[200200];
int len;
set<long long> S[4][4];
long long dp[4][4][80];
;
void add(long long &val, char ch) {
  val *= 4;
  val += ch - 'A';
}
void go(int t) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) S[i][j].clear();
  memset(qnt, 0, sizeof(qnt));
  long long hash = 0;
  for (int i = 1; i < t - 1; i++) add(hash, str[i]);
  for (int i = 0; i < len - t + 1; i++) {
    S[str[i] - 'A'][str[i + t - 1] - 'A'].insert(hash);
    add(hash, str[i + t - 1]);
    hash &= (1 << (2 * t - 4)) - 1;
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) qnt[i][j] = S[i][j].size();
}
long long ans[4][4];
long long aux[4][4];
long long eval(long long t) {
  t--;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) ans[i][j] = ((i == j) ? 1 : (1ll << 61));
  for (int k = 0; k < 63; k++)
    if (t & (1ll << k)) {
      for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
          aux[i][j] = (1ll << 61);
          for (int l = 0; l < 4; l++)
            aux[i][j] = min(aux[i][j], ans[i][l] + dp[l][j][k]);
        }
      for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) ans[i][j] = aux[i][j];
    }
  long long r = (1ll << 61), ii, jj;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) r = min(r, ans[i][j]);
  ("eval %lld -> %lld\n", t, r);
  return r;
}
int main() {
  long long n;
  scanf("%lld %s", &n, str);
  len = strlen(str);
  int t = 1, foi = 0;
  while (!foi) {
    t++;
    go(t);
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++)
        if (qnt[i][j] != (1 << (2 * t - 4))) foi = 1;
  }
  t--;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) dist[i][j] = (1ll << 61);
  go(t + 2);
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (qnt[i][j] != (1 << (2 * t))) dist[i][j] = t + 1;
  go(t + 1);
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (qnt[i][j] != (1 << (2 * t - 2))) dist[i][j] = t;
  ("t = %d\n", t);
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      ("d[%c][%c] = %lld\n", 'A' + i, 'A' + j, dist[i][j]);
  for (int k = 0; k < 80; k++)
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) {
        if (k == 0) {
          dp[i][j][k] = dist[i][j];
          continue;
        }
        dp[i][j][k] = (1ll << 61);
        for (int l = 0; l < 4; l++)
          dp[i][j][k] = min(dp[i][j][k], dp[i][l][k - 1] + dp[l][j][k - 1]);
      }
  long long lo = 1, hi = (1ll << 61);
  while (lo < hi) {
    long long mid = (lo + hi + 1) / 2;
    if (eval(mid) <= n)
      lo = mid;
    else
      hi = mid - 1;
  }
  printf("%lld\n", hi);
}
