#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
char s[N];
int ch[N * 32][4];
int nd, n;
long long wzp;
struct Mat {
  long long a[4][4];
  Mat() { memset(a, 0, sizeof(a)); }
  Mat operator*(const Mat &b) const {
    Mat c;
    for (int i = (int)(0); i <= (int)(3); i++)
      for (int j = (int)(0); j <= (int)(3); j++) {
        c.a[i][j] = (1ll << 60);
        for (int k = (int)(0); k <= (int)(3); k++)
          c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
      }
    return c;
  }
} p[66];
void dfs(int x, int s, int d) {
  for (int i = (int)(0); i <= (int)(3); i++)
    if (ch[x][i])
      dfs(ch[x][i], s, d + 1);
    else
      p[0].a[s][i] = min(p[0].a[s][i], 1ll * d);
}
bool check(Mat x, long long v) {
  for (int i = (int)(0); i <= (int)(3); i++)
    for (int j = (int)(0); j <= (int)(3); j++)
      if (x.a[i][j] <= v) return 1;
  return 0;
}
int main() {
  scanf("%lld%s", &wzp, s + 1);
  n = strlen(s + 1);
  for (int i = (int)(1); i <= (int)(n); i++) s[i] -= 'A';
  for (int i = (int)(1); i <= (int)(n); i++) {
    int x = 0;
    for (int j = (int)(i); j <= (int)(min(i + 30, n)); j++) {
      if (!ch[x][s[j]]) ch[x][s[j]] = ++nd;
      x = ch[x][s[j]];
    }
  }
  for (int i = (int)(0); i <= (int)(3); i++)
    for (int j = (int)(0); j <= (int)(3); j++) p[0].a[i][j] = (1ll << 60);
  for (int i = (int)(0); i <= (int)(3); i++)
    if (ch[0][i]) dfs(ch[0][i], i, 1);
  int tp = 0;
  for (;;) {
    p[tp + 1] = p[tp] * p[tp];
    if (!check(p[tp + 1], wzp)) break;
    tp++;
  }
  Mat x, y;
  long long ans = 0;
  for (; tp >= 0; tp--)
    if (check(y = x * p[tp], wzp - 1)) ans += (1ll << tp), x = y;
  printf("%lld\n", ans + 1);
}
