#include <bits/stdc++.h>
using namespace std;
const unsigned long long int INF = 8000000000000000000;
const int MaxN = 100001;
struct node {
  unsigned long long int h[4];
};
struct best {
  unsigned long long int t[4][4];
  best operator+(const best &a) {
    unsigned long long int i, j, p, q;
    best nw;
    for (i = 0; i < 4; i++) {
      for (j = 0; j < 4; j++) {
        p = INF;
        for (q = 0; q < 4; q++) p = min(p, t[i][q] + a.t[q][j]);
        nw.t[i][j] = p - 1;
      }
    }
    return nw;
  }
};
best casebase;
vector<node> T;
node null;
unsigned long long int act[MaxN * 4];
void docasebase(string &a) {
  T.clear();
  null.h[0] = null.h[1] = null.h[2] = null.h[3] = 0;
  T.push_back(null);
  unsigned long long int i, j, p, q, n, t;
  n = a.size();
  for (i = 0; i < 4; i++)
    for (j = 0; j < 4; j++) casebase.t[i][j] = 15;
  for (i = 0; i < n; i++) {
    p = act[i], q = a[i] - 'A';
    if (!T[p].h[q]) {
      T[p].h[q] = T.size();
      T.push_back(null);
    }
    act[i] = T[p].h[q];
  }
  for (t = 0; t < 12; t++) {
    for (i = 0; i + t + 1 < n; i++) {
      p = act[i], q = a[i + t + 1] - 'A';
      if (!T[p].h[q]) {
        T[p].h[q] = T.size();
        T.push_back(null);
      }
    }
    for (i = 0; i + t < n; i++) {
      p = act[i];
      for (j = 0; j < 4; j++) {
        if (!T[p].h[j])
          casebase.t[a[i] - 'A'][j] = min(casebase.t[a[i] - 'A'][j], t + 2);
      }
    }
    for (i = 0; i + t + 1 < n; i++) act[i] = T[act[i]].h[a[i + t + 1] - 'A'];
  }
}
best binpow(unsigned long long int n) {
  if (n == 1) return casebase;
  best z = binpow(n / 2);
  z = (z + z);
  if (n % 2) z = z + casebase;
  return z;
}
unsigned long long int answer(string &a, unsigned long long int n) {
  unsigned long long int m, i, j, p, q, r;
  docasebase(a);
  p = 1, q = n + 1;
  best A;
  while (p < q) {
    m = (p + q) / 2;
    A = binpow(m), r = INF;
    for (i = 0; i < 4; i++)
      for (j = 0; j < 4; j++) {
        r = min(r, A.t[i][j]);
      }
    if (r > n)
      q = m;
    else
      p = m + 1;
  }
  return p;
}
int main() {
  unsigned long long int n;
  string a;
  cin >> n >> a;
  cout << answer(a, n) << "\n";
}
