#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char str[N];
int s[N], n, cnt = 1, num[4][4][16];
long long m;
struct trie {
  int l, s[4];
} t[N * 16];
struct matrix {
  long long a[4][4];
} A;
matrix operator*(matrix a, matrix b) {
  matrix c;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
      c.a[i][j] = m + 1;
      for (int k = 0; k < 4; k++)
        c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
    }
  return c;
}
matrix mpow(matrix a, long long b) {
  b--;
  matrix c = a;
  for (; b; b >>= 1, (a = a * a))
    if (b & 1) c = c * a;
  return c;
}
bool judge(long long num) {
  matrix x = mpow(A, num);
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (x.a[i][j] < m) return true;
  return false;
}
int main() {
  scanf("%lld", &m);
  scanf("%s", str + 1);
  n = strlen(str + 1);
  for (int i = 1; i <= n; i++) s[i] = str[i] - 'A';
  for (int i = 1, p; i <= n; i++) {
    p = 1;
    for (int j = 1; j <= 15 && i + j - 1 <= n; j++) {
      if (!t[p].s[s[i + j - 1]]) {
        t[p].s[s[i + j - 1]] = ++cnt, t[cnt].l = j;
        num[s[i]][s[i + j - 1]][j]++;
      }
      p = t[p].s[s[i + j - 1]];
    }
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 2; k <= 15; k++)
        if (num[i][j][k] != (1 << ((k - 2) * 2))) {
          A.a[i][j] = k - 1;
          break;
        }
  long long l = 1, r = m, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (judge(mid))
      l = mid + 1;
    else
      r = mid;
  }
  printf("%lld\n", l);
  return 0;
}
