#include <bits/stdc++.h>
using namespace std;
struct squ {
  long long s[4][4];
  friend squ operator*(squ u, squ v) {
    squ ret;
    memset(&ret, 0x3f, sizeof(ret));
    for (long long k = 0; k <= 3; k++) {
      for (long long i = 0; i <= 3; i++) {
        for (long long j = 0; j <= 3; j++) {
          ret.s[i][j] = min(ret.s[i][j], u.s[i][k] + v.s[k][j]);
        }
      }
    }
    return ret;
  }
  friend squ operator^(squ x, long long y) {
    squ ret;
    memset(&ret, 0, sizeof(ret));
    while (y) {
      if (y & 1) ret = ret * x;
      x = x * x;
      y >>= 1;
    }
    return ret;
  }
} A, B;
struct apple {
  long long nxt[5];
} tree[1000011 * 4];
long long n, cnt[4][4][111], len, siz = 1, ans;
long long judge(squ u) {
  for (long long i = 0; i <= 3; i++) {
    for (long long j = 0; j <= 3; j++) {
      if (u.s[i][j] < n) return 1;
    }
  }
  return 0;
}
long long ksm(long long x, long long y) {
  long long ret = 1;
  while (y) {
    if (y & 1) ret = ret * x;
    x = x * x;
    y >>= 1;
  }
  return ret;
}
char s[1000011];
signed main() {
  scanf("%lld", &n);
  scanf("%s", s + 1);
  len = strlen(s + 1);
  for (long long i = 1; i <= len; i++) {
    long long now = 1, a = s[i] - 'A';
    for (long long j = i; j <= min(len, i + 20); j++) {
      long long b = s[j] - 'A';
      if (tree[now].nxt[b] == 0) tree[now].nxt[b] = ++siz, cnt[a][b][j - i]++;
      now = tree[now].nxt[b];
    }
  }
  for (long long a = 0; a <= 3; a++) {
    for (long long b = 0; b <= 3; b++) {
      for (long long k = 1; k <= 20; k++) {
        if (cnt[a][b][k] < ksm(4, k - 1)) {
          A.s[a][b] = k;
          break;
        }
      }
    }
  }
  long long head = 1, tail = n, mid;
  while (head <= tail) {
    mid = (head + tail) / 2;
    B = A ^ mid;
    if (judge(B)) {
      ans = mid;
      head = mid + 1;
    } else
      tail = mid - 1;
  }
  printf("%lld", ans + 1);
  return 0;
}
