#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool maxit(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool minit(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
inline long long gint() {
  char c = getchar();
  int f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') {
      f = -1;
    }
    c = getchar();
  }
  long long a = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') {
    a = a * 10 + c - '0';
  }
  return a * f;
}
const int maxn = 100010, inf = 0x3f3f3f3f;
struct State {
  int val, dp[4];
  State *par, *go[4];
  State(int _val) : val(_val), par(0) {
    memset((go), 0, sizeof((go)));
    fill_n(dp, 4, inf);
  }
} * root, *last;
void extend(int w) {
  State* p = last;
  State* np = new State(p->val + 1);
  for (; p && p->go[w] == 0; p = p->par) {
    p->go[w] = np;
  }
  if (p == 0) {
    np->par = root;
  } else {
    State* q = p->go[w];
    if (q->val == p->val + 1) {
      np->par = q;
    } else {
      State* nq = new State(p->val + 1);
      memcpy(nq->go, q->go, sizeof(q->go));
      nq->par = q->par;
      q->par = np->par = nq;
      for (; p && p->go[w] == q; p = p->par) {
        p->go[w] = nq;
      }
    }
  }
  last = np;
}
void rec(State* p) {
  if (p->dp[0] != inf) {
    return;
  }
  for (int i = 0; i < 4; i++) {
    if (p->go[i] == 0) {
      p->dp[i] = 1;
    } else {
      rec(p->go[i]);
    }
  }
  for (int i = 0; i < 4; i++) {
    if (p->go[i]) {
      for (int j = 0; j < 4; j++) {
        minit(p->dp[j], p->go[i]->dp[j] + 1);
      }
    }
  }
}
void build(char* s) {
  root = last = new State(0);
  for (int i = 0; s[i]; i++) {
    extend(s[i] - 'A');
  }
}
typedef unsigned long long Mat[4][4];
const unsigned long long INF = ~0ULL;
void mat_mul(Mat A, Mat B, Mat res) {
  static Mat C;
  for (int i = 0, _end_ = (4); i < _end_; i++)
    for (int j = 0, _end_ = (4); j < _end_; j++) C[i][j] = INF;
  for (int i = 0, _end_ = (4); i < _end_; i++)
    for (int k = 0, _end_ = (4); k < _end_; k++)
      for (int j = 0, _end_ = (4); j < _end_; j++) {
        minit(C[i][j], A[i][k] + B[k][j]);
      }
  memcpy(res, C, sizeof(C));
}
void print(Mat A) {
  for (int i = 0, _end_ = (4); i < _end_; i++) {
    for (int j = 0, _end_ = (4); j < _end_; j++) {
      cerr << A[i][j] << " ";
    }
    cerr << endl;
  }
  cerr << endl;
}
void mat_pow(Mat A, unsigned long long k, Mat res) {
  static Mat a, r;
  memcpy(a, A, sizeof(a));
  memset((r), 0, sizeof((r)));
  while (k) {
    if (k & 1) {
      mat_mul(r, a, r);
    }
    if (!(k >>= 1)) {
      break;
    }
    mat_mul(a, a, a);
  }
  memcpy(res, r, sizeof(r));
}
unsigned long long n;
char s[maxn];
bool test(Mat A) {
  for (int i = 0, _end_ = (4); i < _end_; i++)
    for (int j = 0, _end_ = (4); j < _end_; j++) {
      if (A[i][j] < n) {
        return true;
      }
    }
  return false;
}
Mat A, tmp;
int main() {
  root = last = new State(0);
  n = gint();
  scanf("%s", s);
  for (int i = 0; s[i]; i++) {
    extend(s[i] - 'A');
  }
  rec(root);
  for (int i = 0, _end_ = (4); i < _end_; i++)
    for (int j = 0, _end_ = (4); j < _end_; j++) {
      A[i][j] = root->go[i] ? root->go[i]->dp[j] : 1;
    }
  unsigned long long l = 0, r = n;
  while (l < r) {
    unsigned long long mid = l + (r - l) / 2;
    mat_pow(A, mid, tmp);
    if (test(tmp)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  cout << r << endl;
  return 0;
}
