#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:128000000")
using namespace std;
void solve();
clock_t start;
int main() {
  int t = 1;
  cout.sync_with_stdio(0);
  cout.precision(10);
  cout << fixed;
  start = clock();
  int testNum = 1;
  while (t--) {
    solve();
  }
  return 0;
}
struct my_map {
  int x[4];
  my_map() { memset(x, -1, sizeof x); }
  bool count(int v) { return x[v - 'A'] != -1; }
  int& operator[](int v) { return x[v - 'A']; }
};
struct state {
  int len, link;
  my_map next;
};
const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;
int dp[MAXLEN * 2][4];
void sa_init() {
  sz = last = 0;
  st[0].len = 0;
  st[0].link = -1;
  ++sz;
}
void sa_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p;
  for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link)
    st[p].next[c] = cur;
  if (p == -1)
    st[cur].link = 0;
  else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len)
      st[cur].link = q;
    else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      for (; p != -1 && st[p].next[c] == q; p = st[p].link)
        st[p].next[c] = clone;
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
bool used[2 * MAXLEN];
void dfs(int v) {
  if (used[v]) return;
  used[v] = true;
  vector<int> haveNow(4, 0);
  for (int i = 0; i < 4; ++i) {
    if (!st[v].next.count(i + 'A')) continue;
    pair<char, int> it = make_pair('A' + i, st[v].next[i + 'A']);
    dfs(it.second);
    haveNow[it.first - 'A'] = 1;
    for (int i = 0; i < 4; ++i) {
      dp[v][i] = min(dp[v][i], 1 + dp[it.second][i]);
    }
  }
  for (char c = 'A'; c <= 'D'; ++c)
    if (!haveNow[c - 'A']) {
      dp[v][c - 'A'] = 1;
      for (int i = 0; i < 4; ++i) dp[v][i] = min(dp[v][i], 2);
    }
}
const long long INF = 1000000000000000010;
vector<vector<long long>> powers[70];
long long mult(long long q, long long w) {
  if (q == 0) return 0;
  if (INF / q < w) return INF;
  long long res = q * w;
  if (res > INF) res = INF;
  return res;
}
vector<vector<long long>> mult(vector<vector<long long>> q,
                               vector<vector<long long>> w) {
  vector<vector<long long>> res(q.size(), vector<long long>(q[0].size(), INF));
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
        res[i][j] = min(res[i][j], q[i][k] + w[k][j]);
      }
      if (res[i][j] > INF) res[i][j] = INF;
    }
  return res;
}
long long n;
bool good(vector<vector<long long>> matrix, long long step) {
  vector<vector<long long>> res(4, vector<long long>(4, 0));
  for (int i = 0; i < 70; ++i) {
    if (step & 1) {
      res = mult(res, powers[i]);
    }
    step >>= 1;
  }
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (res[i][j] < n) return false;
    }
  }
  return true;
}
void solve() {
  string t;
  cin >> n >> t;
  sa_init();
  for (int i = 0; i < t.length(); ++i) sa_extend(t[i]);
  vector<vector<long long>> best(4, vector<long long>(4));
  for (char c = 'A'; c <= 'D'; ++c) {
    for (int i = 0; i < sz; ++i)
      for (char z = 'A'; z <= 'D'; ++z) dp[i][z - 'A'] = 1000000000;
    memset(used, false, sizeof used);
    dfs(st[0].next[c]);
    for (char z = 'A'; z <= 'D'; ++z)
      best[z - 'A'][c - 'A'] = dp[st[0].next[c]][z - 'A'];
  }
  powers[0] = best;
  for (int i = 1; i < 70; ++i) {
    powers[i] = mult(powers[i - 1], powers[i - 1]);
  }
  long long l = 0, r = 1e18 + 5;
  while (l + 1 < r) {
    long long m = (l + r) / 2;
    if (good(best, m))
      r = m;
    else
      l = m;
  }
  cout << r;
}
