#include <bits/stdc++.h>
using namespace std;
long long get() {
  char c;
  while (c = getchar(), (c < '0' || c > '9') && (c != '-'))
    ;
  bool flag = (c == '-');
  if (flag) c = getchar();
  long long x = 0;
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - 48;
    c = getchar();
  }
  return flag ? -x : x;
}
void output(long long x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  int len = 0, data[20];
  while (x) {
    data[len++] = x % 10;
    x /= 10;
  }
  if (!len) data[len++] = 0;
  while (len--) putchar(data[len] + 48);
  putchar('\n');
}
const int maxn = 100000;
char s[maxn];
long long dp[60][4][4], dist[4][4], tmp[4][4];
int data[maxn];
int main() {
  long long m = get();
  int n = 0;
  char c;
  while (c = getchar(), c < 'A' || c > 'D')
    ;
  while (c >= 'A' && c <= 'D') {
    s[n++] = c - 'A';
    c = getchar();
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) dp[0][i][j] = -1;
  int current = 16, len = 1;
  while (current) {
    len++;
    int total = 0;
    for (int i = 0; i + len <= n; i++) {
      int h = 0;
      for (int j = 0; j < len; j++) h = h * 4 + s[i + j];
      data[total++] = h;
    }
    sort(data, data + total);
    for (int mask = 0, i = 0; mask < (1 << (len * 2)); mask++) {
      while (i < total && data[i] < mask) i++;
      if (i == total || data[i] != mask) {
        int a = mask >> (len * 2 - 2), b = mask & 3;
        if (dp[0][a][b] == -1) {
          dp[0][a][b] = len - 1;
          current--;
        }
      }
    }
  }
  int t = 0;
  while (true) {
    long long best = dp[t][0][0];
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) best = min(best, dp[t][i][j]);
    if (best >= m) break;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) {
        dp[t + 1][i][j] = dp[t][i][0] + dp[t][0][j];
        for (int k = 1; k < 4; k++)
          dp[t + 1][i][j] = min(dp[t + 1][i][j], dp[t][i][k] + dp[t][k][j]);
      }
    t++;
  }
  memset(dist, 0, sizeof(dist));
  long long ans = 1;
  while (t) {
    t--;
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) {
        tmp[i][j] = dist[i][0] + dp[t][0][j];
        for (int k = 1; k < 4; k++)
          tmp[i][j] = min(tmp[i][j], dist[i][k] + dp[t][k][j]);
      }
    long long best = tmp[0][0];
    for (int i = 0; i < 4; i++)
      for (int j = 0; j < 4; j++) best = min(best, tmp[i][j]);
    if (best < m) {
      for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) dist[i][j] = tmp[i][j];
      ans += 1LL << t;
    }
  }
  output(ans);
  return 0;
}
