#include <bits/stdc++.h>
using namespace std;
const long long inf = 1000000000000000000ll;
long long n;
int len;
long long f[70][4][4], g[4][4];
int nxt[100005 * 13][4], sum[4][4][14], ndsum;
bool vis[100005 * 13];
char a[100005];
void ins(int pos) {
  int now = 0, fir = a[pos] - 'A';
  for (int i = 1; i <= 13 && pos <= len; ++i, ++pos) {
    int c = a[pos] - 'A';
    if (!nxt[now][c]) nxt[now][c] = ++ndsum;
    now = nxt[now][c];
    if (!vis[now]) {
      vis[now] = 1;
      sum[fir][c][i]++;
    }
  }
}
long long solve(long long n) {
  int now = 1;
  memset(g, 0, sizeof(g));
  while (n) {
    if (n & 1) {
      long long pre[4][4];
      for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j) pre[i][j] = g[i][j];
      for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
          long long tmp = inf;
          for (int k = 0; k < 4; ++k) tmp = min(tmp, f[now][i][k] + pre[k][j]);
          g[i][j] = tmp;
        }
      }
    }
    n >>= 1;
    ++now;
  }
  long long ret = inf;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) ret = min(ret, g[i][j]);
  return ret;
}
int main() {
  scanf("%lld%s", &n, a + 1);
  len = strlen(a + 1);
  for (int i = 1; i <= len; ++i) ins(i);
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int l = 2, t = 1; l <= 13; ++l, t *= 4) {
        if (sum[i][j][l] < t) {
          f[1][i][j] = l - 1;
          break;
        }
      }
    }
  }
  for (int t = 2; t <= 64; ++t) {
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        f[t][i][j] = inf;
        for (int k = 0; k < 4; ++k)
          f[t][i][j] = min(f[t][i][j], f[t - 1][i][k] + f[t - 1][k][j]);
      }
    }
  }
  long long l = 1, r = n, ans = 0;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    long long tmp = solve(mid);
    if (tmp < n)
      l = mid + 1;
    else
      r = mid - 1, ans = mid;
  }
  printf("%lld\n", ans);
  return 0;
}
