#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int len, S, T;
bool o[N * 40][15];
char str[N];
long long n, Ans;
struct matrix {
  long long f[4][4];
  matrix() { memset(f, 63, sizeof(f)); }
} Trans, bin[70], X;
void cmin(long long& x, long long y) { x = x < y ? x : y; }
matrix operator*(matrix a, matrix b) {
  matrix c;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j)
      for (int k = 0; k < 4; ++k) cmin(c.f[i][j], a.f[i][k] + b.f[k][j]);
  return c;
}
int bfs() {
  queue<int> q, d;
  q.push(S), d.push(1);
  while (!q.empty()) {
    int u = q.front(), dis = d.front();
    q.pop(), d.pop();
    if (!o[u * 4 + T][dis + 1]) return dis + 1;
    for (int i = 0; i < 4; ++i) {
      int v = u * 4 + i;
      q.push(v), d.push(dis + 1);
    }
  }
  return 233;
}
int main() {
  scanf("%lld", &n);
  scanf("%s", str + 1);
  len = strlen(str + 1);
  for (int i = 1; i <= len; ++i)
    for (int k = 1, tp = 0; i + k - 1 <= len && k <= 10; ++k)
      tp = tp * 4 + str[i + k - 1] - 'A', o[tp][k] = 1;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) S = i, T = j, Trans.f[i][j] = bfs() - 1;
  bin[0] = Trans;
  for (int i = 1; i < 62; ++i) bin[i] = bin[i - 1] * bin[i - 1];
  memset(X.f, 0, sizeof(X.f));
  for (int i = 61; ~i; --i) {
    matrix tmp = X * bin[i];
    long long mn = 2e18;
    for (int j = 0; j < 4; ++j)
      for (int k = 0; k < 4; ++k) cmin(mn, tmp.f[j][k]);
    if (mn < n) X = tmp, Ans += 1ll << i;
  }
  ++Ans;
  printf("%lld", Ans);
  return 0;
}
