#include <bits/stdc++.h>
using namespace std;
char buf[100010];
int N;
int a[100010];
int four[20];
bool found[(1 << 20)];
int graph[4][4];
void check(int d) {
  int i, j;
  for ((i) = 0; (i) < (int)(four[d]); (i)++) found[i] = false;
  for ((i) = 0; (i) < (int)(N - d + 1); (i)++) {
    int tmp = 0;
    for ((j) = 0; (j) < (int)(d); (j)++) tmp = tmp * 4 + a[i + j];
    found[tmp] = true;
  }
  for ((i) = 0; (i) < (int)(four[d]); (i)++)
    if (!found[i]) {
      int s = i / four[d - 1];
      int t = i % 4;
      graph[s][t] = min(graph[s][t], d - 1);
    }
}
struct matrix {
  long long a[4][4];
};
matrix prod(matrix A, matrix B) {
  matrix C;
  int i, j, k;
  for ((i) = 0; (i) < (int)(4); (i)++)
    for ((j) = 0; (j) < (int)(4); (j)++) C.a[i][j] = (1ll << 60);
  for ((i) = 0; (i) < (int)(4); (i)++)
    for ((j) = 0; (j) < (int)(4); (j)++)
      for ((k) = 0; (k) < (int)(4); (k)++)
        C.a[i][k] = min(C.a[i][k], A.a[i][j] + B.a[j][k]);
  return C;
}
long long shortest_path(long long K) {
  int i, j;
  matrix A;
  for ((i) = 0; (i) < (int)(4); (i)++)
    for ((j) = 0; (j) < (int)(4); (j)++) A.a[i][j] = graph[i][j];
  matrix O;
  for ((i) = 0; (i) < (int)(4); (i)++)
    for ((j) = 0; (j) < (int)(4); (j)++) O.a[i][j] = 0;
  for ((i) = 0; (i) < (int)(60); (i)++) {
    if (K & (1ll << i)) O = prod(O, A);
    A = prod(A, A);
  }
  long long ans = (1ll << 60);
  for ((i) = 0; (i) < (int)(4); (i)++)
    for ((j) = 0; (j) < (int)(4); (j)++) ans = min(ans, O.a[i][j]);
  return ans;
}
int main(void) {
  int i, j;
  long long X;
  cin >> X;
  scanf("%s", buf);
  while (buf[N] != '\0') {
    a[N] = buf[N] - 'A';
    N++;
  }
  for ((i) = 0; (i) < (int)(16); (i)++) four[i] = (1 << (2 * i));
  for ((i) = 0; (i) < (int)(4); (i)++)
    for ((j) = 0; (j) < (int)(4); (j)++) graph[i][j] = 10;
  for (i = 2; i <= 10; i++) check(i);
  long long low = 0, high = (1ll << 60);
  while (high - low > 1) {
    long long mid = (low + high) / 2;
    long long tmp = shortest_path(mid);
    if (tmp <= X - 1)
      low = mid;
    else
      high = mid;
  }
  cout << low + 1 << endl;
  return 0;
}
