#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
long long n, ans = 0;
char s[N];
int len = 0, mx;
int tot = 0, ch[4][N * 20];
int dis[30][4][4];
struct mtrx {
  long long a[4][4];
};
mtrx f[64], Now, tmp;
template <typename T>
inline T Min(const T &x, const T &y) {
  return x < y ? x : y;
}
void build(int l, int r) {
  int u = 0;
  for (int i = l; i <= r; i++) {
    if (!ch[s[i] - 'A'][u]) {
      ch[s[i] - 'A'][u] = ++tot;
      ++dis[i - l][s[l] - 'A'][s[i] - 'A'];
    }
    u = ch[s[i] - 'A'][u];
  }
}
mtrx operator*(const mtrx &x, const mtrx &y) {
  mtrx res;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
      res.a[i][j] = 8e18;
      for (int k = 0; k < 4; k++)
        res.a[i][j] = Min(res.a[i][j], x.a[i][k] + y.a[k][j]);
    }
  return res;
}
bool check(mtrx x) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (x.a[i][j] < n) return 0;
  return 1;
}
int main() {
  scanf("%I64d", &n), scanf("%s", s + 1), len = strlen(s + 1);
  for (int i = 1; i <= len; i++) build(i, Min(i + 19, len));
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
      int k = 1;
      for (; dis[k][i][j] >= (1 << (k - 1 << 1)); ++k)
        ;
      f[0].a[i][j] = k;
    }
  for (mx = 1; mx <= 64; mx++) {
    f[mx] = f[mx - 1] * f[mx - 1];
    if (check(f[mx])) break;
  }
  for (int i = mx; ~i; i--) {
    tmp = Now * f[i];
    if (!check(tmp)) ans += (1ll << i), Now = tmp;
  }
  printf("%I64d\n", ans + 1);
  return 0;
}
