#include <bits/stdc++.h>
using namespace std;
string s;
int m, len[4][4];
bool vis[1100000];
long long n;
struct matrix {
  long long a[4][4];
  matrix operator*(const matrix B) {
    matrix C;
    memset(C.a, 0x3f, sizeof(C.a));
    for (int i = (0); i <= (3); i++)
      for (int j = (0); j <= (3); j++)
        for (int k = (0); k <= (3); k++)
          C.a[i][j] = min(C.a[i][j], a[i][k] + B.a[k][j]);
    return C;
  }
};
void cal_dis() {
  for (int i = (0); i <= (3); i++)
    for (int j = (0); j <= (3); j++) len[i][j] = 10;
  for (int d = (1); d <= (9); d++) {
    for (int i = (0); i <= (1 << (2 * d + 2)); i++) vis[i] = false;
    for (int i = (0); i <= (m - d - 1); i++) {
      int num = 0;
      for (int j = (0); j <= (d); j++) num = num * 4 + (s[i + j] - 'A');
      vis[num] = true;
    }
    for (int i = (0); i <= (1 << (2 * d + 2)); i++)
      if (!vis[i]) {
        int s = i / (1 << (2 * d)), t = i % 4;
        len[s][t] = min(len[s][t], d);
      }
  }
}
long long shortest_path(long long step) {
  matrix A, O;
  for (int i = (0); i <= (3); i++)
    for (int j = (0); j <= (3); j++) A.a[i][j] = len[i][j];
  memset(O.a, 0, sizeof(O.a));
  for (; step; step >>= 1) {
    if (step & 1) O = O * A;
    A = A * A;
  }
  long long ret = 0x3f3f3f3f3f3f3f3f;
  for (int i = (0); i <= (3); i++)
    for (int j = (0); j <= (3); j++) ret = min(ret, O.a[i][j]);
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> s;
  m = s.size();
  cal_dis();
  long long l = 0, r = 0x3f3f3f3f3f3f3f3f, mid;
  while (l < r - 1) {
    mid = (l + r) >> 1;
    if (shortest_path(mid) < n)
      l = mid;
    else
      r = mid;
  }
  cout << l + 1 << endl;
  return 0;
}
