#include <bits/stdc++.h>
using namespace std;
int nas[4][100015];
char napi[100015];
struct Ukkonen {
  static const int max_len = 200000;
  struct node {
    map<char, pair<node *, pair<int, int> > > trans;
    node *suflink;
    int szukaj(char D) {
      int w = max_len + 100;
      for (int i = 'A'; i <= 'D'; i++) {
        if (trans.find(i) == trans.end() && i == D) return 0;
        w = min(w, licz(i, D));
      }
      return w;
    }
    int licz(char A, char D) {
      map<char, pair<node *, pair<int, int> > >::iterator it = trans.find(A);
      if (it == trans.end()) return max_len + 10;
      pair<node *, pair<int, int> > t = (*it).second;
      if (t.second.first == t.second.second) {
        if (t.first == nullptr) return 1;
        return t.first->szukaj(D) + 1;
      }
      int z = t.second.second;
      for (int i = 'A'; i <= 'D'; i++) {
        if (i == D) continue;
        z = min(z, nas[i - 'A'][t.second.first + 1]);
      }
      if (napi[z] == D) {
        if (t.first == nullptr) return t.second.second - t.second.first;
        return t.first->szukaj(D) + t.second.second - t.second.first;
      }
      return z - t.second.first;
    }
  };
  int n;
  char nap[max_len + 5];
  node *root;
  node *pin;
  Ukkonen() : n(0), root(nullptr), pin(nullptr) {}
  void kanonizuj(node *&s, int &a, int b) {
    if (b < a) return;
    pair<node *, pair<int, int> > t = s->trans[nap[a]];
    node *sp = t.first;
    int ap = t.second.first;
    int bp = t.second.second;
    while (bp - ap <= b - a) {
      a = a + bp - ap + 1;
      s = sp;
      if (a <= b) {
        t = s->trans[nap[a]];
        sp = t.first;
        ap = t.second.first;
        bp = t.second.second;
      }
    }
  }
  bool splituj(node *s, int a, int b, char c, node *&ret) {
    if (a <= b) {
      pair<node *, pair<int, int> > &t = s->trans[nap[a]];
      node *sp = t.first;
      int ap = t.second.first;
      int bp = t.second.second;
      if (c == nap[ap + b - a + 1]) {
        ret = s;
        return true;
      }
      ret = new node();
      t.second.second = ap + b - a;
      t.first = ret;
      ret->trans[nap[ap + b - a + 1]] =
          make_pair(sp, make_pair(ap + b - a + 1, bp));
      return false;
    }
    ret = s;
    return s->trans.find(c) != s->trans.end();
  }
  void update(node *&s, int &a, int &i) {
    node *oldr = root;
    node *r;
    bool end = splituj(s, a, i - 1, nap[i], r);
    while (!end) {
      r->trans[nap[i]] = make_pair(nullptr, make_pair(i, n));
      if (oldr != root) oldr->suflink = r;
      oldr = r;
      s = s->suflink;
      kanonizuj(s, a, i - 1);
      end = splituj(s, a, i - 1, nap[i], r);
    }
    if (oldr != root) oldr->suflink = s;
  }
  void konstruuj() {
    root = new node();
    pin = new node();
    for (int i = 1; i <= n; i++)
      pin->trans[nap[i]] = make_pair(root, make_pair(i, i));
    root->suflink = pin;
    node *s = root;
    int a = 1;
    for (int i = 1; i <= n; i++) {
      update(s, a, i);
      kanonizuj(s, a, i);
    }
  }
};
const long long int infty = 2e18;
long long int dodaj(const long long int &a, const long long int &b) {
  const long long int &x = a + b;
  if (x > infty) return infty;
  return x;
}
long long int pomnoz(long long int a, long long int b) {
  long long int wyn = 0LL;
  while (b) {
    if (b % 2 == 1) wyn = dodaj(wyn, a);
    a = dodaj(a, a);
    b /= 2;
  }
  return wyn;
}
long long int tab[4][4];
long long int mnoz[10][4][4];
long long int n;
void dawaj(int a, int b, int c) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) mnoz[c][i][j] = n + 1;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 0; k < 4; k++)
        mnoz[c][i][j] = min(mnoz[c][i][j], dodaj(mnoz[a][i][k], mnoz[b][k][j]));
}
bool ok(long long int c) {
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      mnoz[0][i][j] = 0;
      mnoz[2][i][j] = tab[i][j];
    }
  }
  for (int i = 0; i < 4; i++) mnoz[0][i][i] = 1;
  int w = 0, g = 2;
  c--;
  while (c) {
    if (c % 2 == 1) {
      dawaj(w, g, w ^ 1);
      w ^= 1;
    }
    dawaj(g, g, g ^ 1);
    g ^= 1;
    c /= 2;
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (mnoz[w][i][j] < n) return true;
  return false;
}
int main() {
  Ukkonen u;
  scanf("%lld", &n);
  scanf("%s", u.nap + 1);
  u.n = strlen(u.nap + 1);
  for (int i = 1; i <= u.n; i++) napi[i] = u.nap[i];
  for (int i = 0; i < 4; i++) nas[i][u.n + 1] = u.n + 3;
  for (int i = u.n; i >= 1; i--) {
    for (int j = 0; j < 4; j++) nas[j][i] = nas[j][i + 1];
    nas[u.nap[i] - 'A'][i] = i;
  }
  u.konstruuj();
  for (int i = 'A'; i <= 'D'; i++)
    for (int j = 'A'; j <= 'D'; j++) tab[i - 'A'][j - 'A'] = u.root->licz(i, j);
  long long int a = 1LL, b = n, c;
  while (a < b) {
    c = (a + b + 1) / 2;
    if (ok(c))
      a = c;
    else
      b = c - 1;
  }
  printf("%lld\n", a);
  return 0;
}
