#include <bits/stdc++.h>
using namespace std;
long long n;
string t;
struct vertex {
  int to[4], l[4], r[4];
  int parent;
  int height;
} stree[500000];
int ssz = 1;
int suff[500000];
void init(int k) {
  memset(stree[k].to, -1, sizeof stree[k].to);
  suff[k] = -1;
  stree[k].height = 0;
  stree[k].parent = 0;
}
int new_vertex(int p) {
  init(ssz);
  stree[ssz].parent = p;
  return ssz++;
}
int split(int v, int c, int l) {
  if (l == 0) return v;
  if (l == stree[v].r[c] - stree[v].l[c]) return stree[v].to[c];
  int r = new_vertex(v), tp = t[stree[v].l[c] + l] - 'A';
  stree[r].to[tp] = stree[v].to[c];
  stree[r].r[tp] = stree[v].r[c];
  stree[r].l[tp] = stree[v].l[c] + l;
  stree[v].r[c] = stree[v].l[c] + l;
  stree[v].to[c] = r;
  stree[stree[r].to[tp]].parent = r;
  stree[r].height = stree[v].height + l;
  return r;
}
int add_leaf(int v, int c, int l) {
  int r = new_vertex(v);
  stree[v].to[c] = r;
  stree[v].l[c] = l;
  stree[v].r[c] = t.size();
  stree[r].height = t.size() - l - 1 + stree[v].height;
  return r;
}
bool try_c(int vpos, int epos, int cpos, int c) {
  if (epos == 0) {
    return stree[vpos].to[c] != -1;
  } else
    return t[stree[vpos].l[cpos] + epos] == c + 'A';
}
void jump(int& vpos, int& epos, int& cpos, int l, int r) {
  epos = r - l - stree[vpos].height;
  while (stree[vpos].to[cpos] != -1 &&
         epos >= stree[vpos].r[cpos] - stree[vpos].l[cpos]) {
    int len = stree[vpos].r[cpos] - stree[vpos].l[cpos];
    vpos = stree[vpos].to[cpos];
    epos -= len;
    cpos = t[stree[vpos].height + l] - 'A';
  }
}
typedef long long mtr[4][4];
int nst[500000][4];
int pr[4][4];
long long minn(mtr a) {
  long long ans = 1LL << 62;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) ans = min(ans, a[i][j]);
  return ans;
}
void multiply(mtr a, mtr b, mtr c) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
      c[i][j] = 1LL << 62;
      for (int k = 0; k < 4; k++) {
        c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
      }
    }
}
void eq(mtr a) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) a[i][j] = (i == j);
}
void cp(mtr a, mtr b) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) b[i][j] = a[i][j];
}
void pow(mtr ao, long long p, mtr r) {
  eq(r);
  mtr buf, a;
  cp(ao, a);
  while (p > 0) {
    if (p % 2 == 1) {
      p--;
      cp(r, buf);
      multiply(a, buf, r);
    } else {
      multiply(a, a, buf);
      cp(buf, a);
      p /= 2;
    }
  }
}
long long ord[4][4];
void relax(long long& v, long long c) {
  if (v == -1)
    v = c;
  else
    v = min(v, c);
}
void mindist(int v, long long res[4]);
void mindist(int v, int c, long long res[4]) {
  for (int i = 0; i < 4; i++) {
    int ns = nst[stree[v].l[c] + 1][i];
    if (ns != -1 && ns < stree[v].r[c]) {
      relax(res[i], ns - stree[v].l[c] + stree[v].height);
    }
  }
  mindist(stree[v].to[c], res);
}
void mindist(int v, long long res[4]) {
  for (int i = 0; i < 4; i++) {
    if (stree[v].to[i] == -1) {
      relax(res[i], stree[v].height);
    } else {
      mindist(v, i, res);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  cin >> t;
  int l = 0, r = 0;
  init(0);
  suff[0] = 0;
  int vpos = 0;
  int cpos = 0;
  int epos = 0;
  int alone = -1;
  while (l < t.size() && r < t.size()) {
    int c = t[r] - 'A';
    while (l <= r && !try_c(vpos, epos, cpos, c)) {
      int b = split(vpos, cpos, epos);
      if (alone != -1) {
        suff[alone] = b;
        alone = -1;
      }
      if (suff[b] == -1) alone = b;
      add_leaf(b, c, r);
      l++;
      vpos = suff[vpos];
      cpos = t[l + stree[vpos].height] - 'A';
      if (l <= r) jump(vpos, epos, cpos, l, r);
    }
    if (alone != -1) {
      suff[alone] = vpos;
      alone = -1;
    }
    r++;
    if (l != r) jump(vpos, epos, cpos, l, r);
  }
  for (int i = 0; i < 4; i++) nst[t.size()][i] = -1;
  for (int i = t.size() - 1; i >= 0; i--)
    for (int j = 0; j < 4; j++) {
      if (j + 'A' == t[i])
        nst[i][j] = nst[i + 1][j];
      else
        nst[i][j] = i;
    }
  {
    memset(ord, -1, sizeof ord);
    for (int i = 0; i < 4; i++)
      if (stree[0].to[i] != -1) mindist(0, i, ord[i]);
  }
  {
    long long l = 0, r = n;
    mtr res;
    while (l + 1 < r) {
      long long m = (l + r) / 2;
      pow(ord, m, res);
      if (minn(res) <= n - 1)
        l = m;
      else
        r = m;
    }
    cout << l + 1;
  }
}
