#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10;
const int MAXPOOL = MAXN * 2;
const int INF = 0x3f3f3f3f;
struct Matrix {
  long long map[4][4];
  Matrix() { memset(map, 0, sizeof(map)); }
  Matrix operator*(const Matrix& a) const {
    Matrix b;
    memset(b.map, 0x3f, sizeof(b.map));
    for (int i = 0; i < 4; ++i)
      for (int k = 0; k < 4; ++k)
        for (int j = 0; j < 4; ++j)
          b.map[i][j] = min(b.map[i][j], map[i][k] + a.map[k][j]);
    return b;
  }
  long long calc() { return *min_element(map[0], map[3] + 4); }
  void print() {
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) cerr << map[i][j] << ' ';
      cerr << endl;
    }
  }
};
Matrix qpow(Matrix a, long long b) {
  Matrix ans;
  for (int i = 0; i < 4; ++i) ans.map[i][i] = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}
struct SuffixAutomaton {
  int alloc, last;
  int fa[MAXPOOL], ch[MAXPOOL][4];
  int len[MAXPOOL];
  void init() { alloc = last = 1; }
  void extend(int c) {
    c -= 'A';
    int p = last, np = ++alloc;
    last = np;
    len[np] = len[p] + 1;
    while (p && !ch[p][c]) ch[p][c] = np, p = fa[p];
    if (!p)
      fa[np] = 1;
    else {
      int q = ch[p][c];
      if (len[q] == len[p] + 1)
        fa[np] = q;
      else {
        int nq = ++alloc;
        memcpy(ch[nq], ch[q], sizeof(ch[nq]));
        fa[nq] = fa[q];
        len[nq] = len[p] + 1;
        fa[np] = fa[q] = nq;
        while (p && ch[p][c] == q) ch[p][c] = nq, p = fa[p];
      }
    }
  }
  int f[MAXPOOL][4];
  bool vis[MAXPOOL];
  void dfs(int p) {
    if (vis[p]) return;
    vis[p] = true;
    for (int i = 0; i < 4; ++i)
      if (ch[p][i]) {
        dfs(ch[p][i]);
        f[p][i] = INF;
      }
    for (int i = 0; i < 4; ++i) {
      if (!ch[p][i]) {
        f[p][i] = 1;
      } else {
        for (int j = 0; j < 4; ++j) {
          f[p][j] = min(f[p][j], f[ch[p][i]][j] + 1);
        }
      }
    }
  }
  Matrix build(char str[]) {
    init();
    for (int i = 0; str[i]; ++i) extend(str[i]);
    dfs(1);
    Matrix res;
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j) res.map[i][j] = f[ch[1][i]][j];
    return res;
  }
} sam;
int main() {
  ios::sync_with_stdio(0);
  long long n;
  char str[MAXN];
  cin >> n;
  cin >> str;
  Matrix A = sam.build(str);
  long long l = 1, r = n, ans = 0;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (qpow(A, mid).calc() >= n)
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  cout << ans;
}
