#include <bits/stdc++.h>
using namespace std;
string s;
long long n;
int a[5000010][4], sz;
struct Matrix {
  long long v[4][4];
  Matrix(long long num = 0) {
    for (int i = 0; i <= 3; i++)
      for (int j = 0; j <= 3; j++) v[i][j] = num;
  }
} M[60];
inline Matrix operator*(Matrix &a, Matrix &b) {
  Matrix res = Matrix(0x3f3f3f3f3f3f3f3fll);
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++)
      for (int k = 0; k <= 3; k++)
        res.v[i][j] = min(res.v[i][j], a.v[i][k] + b.v[k][j]);
  return res;
}
inline void insert(string s) {
  int now = 0, l = s.size();
  for (int i = 0; i < l && i < 20; i++) {
    int p = s[i] - 'A';
    if (!a[now][p]) a[now][p] = ++sz;
    now = a[now][p];
  }
}
inline void dfs(int i, int j, int x, long long dep) {
  if (!a[x][j]) {
    M[1].v[i][j] = min(M[1].v[i][j], dep);
    return;
  }
  for (int p = 0; p <= 3; p++) {
    if (a[x][p]) dfs(i, j, a[x][p], dep + 1);
  }
}
inline bool check(Matrix M) {
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) {
      if (M.v[i][j] < n) return false;
    }
  return true;
}
int main() {
  scanf("%lld", &n);
  cin >> s;
  int l = s.size();
  for (int i = 0; i < l; i++) {
    string ss = s.substr(i, l - i);
    insert(ss);
  }
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) {
      M[1].v[i][j] = 0x3f3f3f3f3f3f3f3fll;
      if (a[0][i]) dfs(i, j, a[0][i], 1);
    }
  for (int i = 2; i <= 60; i++) M[i] = M[i - 1] * M[i - 1];
  Matrix now = Matrix(0x3f3f3f3f3f3f3f3fll);
  for (int i = 0; i <= 3; i++) now.v[i][i] = 0;
  long long len = 0;
  for (int i = 60; i >= 1; i--) {
    Matrix tmp = now * M[i];
    if (check(tmp)) continue;
    now = tmp;
    len += (1ll << (i - 1));
  }
  printf("%lld\n", len + 1);
  return 0;
}
