#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
const int N = 200000 + 5;
const long long INF = (long long)2000000000 * 1000000000;
int l[N][4];
char s[N];
int n;
int link[N], len[N], ne[N][4], pos[N];
vector<int> graph[N];
int sa, last;
long long E[4][4];
int V;
void extend(char c) {
  int cur = sa++;
  pos[cur] = V;
  len[cur] = len[last] + 1;
  int p;
  for (p = last; p != -1 && !ne[p][c]; p = link[p]) ne[p][c] = cur;
  if (p == -1) {
    link[cur] = 0;
  } else {
    int q = ne[p][c];
    if (len[p] + 1 == len[q]) {
      link[cur] = q;
    } else {
      int clone = sa++;
      len[clone] = len[p] + 1;
      for (int j = 0; j < (int)(4); ++j) ne[clone][j] = ne[q][j];
      link[clone] = link[q];
      for (; p != -1 && ne[p][c] == q; p = link[p]) ne[p][c] = clone;
      link[q] = link[cur] = clone;
    }
  }
  last = cur;
}
bool mark[N];
void dfs(int v) {
  mark[v] = true;
  for (int j = 0; j < (int)(((int)((graph[v]).size()))); ++j) {
    int to = graph[v][j];
    if (mark[to]) continue;
    dfs(to);
    if (!pos[v]) pos[v] = pos[to];
  }
}
void suffix_automata() {
  sa = last = 0;
  len[0] = 0;
  link[0] = -1;
  ++sa;
  for (int i = 0; i < (int)(n); ++i) {
    V = i + 1;
    extend(s[i]);
  }
  for (int i = 0; i < (int)(sa); ++i)
    if (link[i] != -1) graph[link[i]].push_back(i);
  dfs(0);
  for (int i = 1; i <= (int)(sa - 1); ++i) {
    for (int u = 0; u < (int)(4); ++u) {
      if (!ne[i][u]) {
        int len1 = len[i], len2 = len[link[i]];
        int j = pos[i] - len2;
        for (int v = 0; v < (int)(4); ++v) {
          if (pos[i] - l[j][v] <= len1) {
            E[v][u] = min(E[v][u], (long long)pos[i] - l[j][v]);
          }
        }
      }
    }
  }
}
struct coord {
  long long r[4][4];
  void init() {
    for (int u = 0; u < (int)(4); ++u)
      for (int v = 0; v < (int)(4); ++v) r[u][v] = E[u][v];
  }
};
coord S;
coord F(coord a, coord b) {
  coord c;
  for (int u = 0; u < (int)(4); ++u)
    for (int v = 0; v < (int)(4); ++v) c.r[u][v] = INF;
  for (int u = 0; u < (int)(4); ++u)
    for (int v = 0; v < (int)(4); ++v)
      for (int t = 0; t < (int)(4); ++t)
        c.r[u][v] = min(c.r[u][v], a.r[u][t] + b.r[t][v]);
  return c;
}
coord getfor(long long k) {
  if (k == 1) return S;
  if (k % 2 == 0) {
    coord p = getfor(k / 2);
    return F(p, p);
  }
  return F(getfor(k - 1), S);
}
coord binpow(coord S, long long n) {
  coord res;
  for (int u = 0; u < (int)(4); ++u)
    for (int v = 0; v < (int)(4); ++v) res.r[u][v] = 0;
  while (n) {
    if (n % 2 == 1) {
      res = F(res, S);
    }
    S = F(S, S);
    n /= 2;
  }
  return res;
}
long long getwith(long long k) {
  long long res = INF;
  coord val = binpow(S, k);
  for (int u = 0; u < (int)(4); ++u)
    for (int v = 0; v < (int)(4); ++v) res = min(res, val.r[u][v]);
  return res;
}
void solve() {
  long long m;
  cin >> m;
  scanf("%s", s);
  n = strlen(s);
  for (int i = 0; i < (int)(n); ++i) s[i] -= 'A';
  int re[4];
  for (int j = 0; j < (int)(4); ++j) re[j] = -1;
  for (int i = 0; i < (int)(n + 1); ++i) {
    for (int j = 0; j < (int)(4); ++j) l[i][j] = re[j];
    if (i != n) re[s[i]] = i;
  }
  for (int u = 0; u < (int)(4); ++u)
    for (int v = 0; v < (int)(4); ++v) E[u][v] = INF;
  suffix_automata();
  long long s = 0, f = m, ans = m;
  S.init();
  while (s <= f) {
    long long md = (s + f) / 2;
    if (getwith(md) >= m) {
      ans = md;
      f = md - 1;
    } else {
      s = md + 1;
    }
  }
  cout << ans << endl;
}
void testgen() {}
int main() {
  cout << fixed;
  cout.precision(12);
  cerr << fixed;
  cerr.precision(3);
  solve();
  return 0;
}
