#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void ckmin(T &a, U b) {
  if (a > b) a = b;
}
template <class T, class U>
void ckmax(T &a, U b) {
  if (a < b) a = b;
}
const int MOD = 1000000933, MOD1 = 1000000931;
const int CO = 1000003;
int add(int a, int b, int INF) {
  a += b;
  if (a >= INF) a -= INF;
  return a;
}
int mul(int a, int b, int INF) { return (long long)a * b % INF; }
int sub(int a, int b, int INF) {
  a -= b;
  if (a < 0) a += INF;
  return a;
}
int pwr(int a, int b, int INF) {
  int res = 1;
  while (b) {
    if (b & 1) res = mul(res, a, INF);
    a = mul(a, a, INF);
    b >>= 1;
  }
  return res;
}
long long K;
int N;
vector<int> arr;
set<pair<int, int> > hsh;
array<array<long long, 4>, 4> dist;
array<array<long long, 4>, 4> trans[62];
array<array<long long, 4>, 4> mul(array<array<long long, 4>, 4> a,
                                  array<array<long long, 4>, 4> b) {
  array<array<long long, 4>, 4> res;
  for (auto j = (0); j < (4); j++) {
    for (auto k = (0); k < (4); k++) {
      res[j][k] = K + 1;
      for (auto i = (0); i < (4); i++) {
        ckmin(res[j][k], a[j][i] + b[i][k]);
      }
    }
  }
  return res;
}
int32_t main() {
  cout << fixed << setprecision(12);
  cerr << fixed << setprecision(4);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> K;
  string temps;
  cin >> temps;
  N = ((int)(temps).size());
  arr.resize(N);
  for (auto i = (0); i < (N); i++) {
    arr[i] = (temps[i] - 'A');
  }
  for (auto i = (0); i < (N); i++) {
    pair<int, int> h = make_pair(0, 0);
    for (int j = i; j <= i + 12 && j < N; j++) {
      h.first = mul(h.first, CO, MOD);
      h.first = add(h.first, arr[j] + 1, MOD);
      h.second = mul(h.second, CO, MOD1);
      h.second = add(h.second, arr[j] + 1, MOD1);
      hsh.insert(h);
    }
  }
  for (auto i = (0); i < (4); i++) {
    for (auto j = (0); j < (4); j++) {
      dist[i][j] = 11;
      for (auto k = (0); k < (10); k++) {
        bool ok = false;
        for (auto m = (0); m < ((1 << (2 * k))); m++) {
          pair<int, int> h = {i + 1, i + 1};
          for (auto n = (0); n < (k); n++) {
            bool b1 = (m & (1 << (2 * n)));
            bool b2 = (m & (1 << (2 * n + 1)));
            h.first = mul(h.first, CO, MOD);
            h.first = add(h.first, 2 * b1 + b2 + 1, MOD);
            h.second = mul(h.second, CO, MOD1);
            h.second = add(h.second, 2 * b1 + b2 + 1, MOD1);
          }
          h.first = mul(h.first, CO, MOD);
          h.first = add(h.first, j + 1, MOD);
          h.second = mul(h.second, CO, MOD1);
          h.second = add(h.second, j + 1, MOD1);
          if (!hsh.count(h)) {
            ok = true;
            break;
          }
        }
        if (ok) {
          dist[i][j] = k + 1;
          break;
        }
      }
    }
  }
  trans[0] = dist;
  for (auto i = (1); i < (62); i++) {
    trans[i] = mul(trans[i - 1], trans[i - 1]);
  }
  long long ans = 0;
  for (auto i = (0); i < (4); i++) {
    for (auto j = (0); j < (4); j++) {
      dist[i][j] = 0;
    }
  }
  K--;
  for (auto i = (61) - 1; i >= (0); i--) {
    auto d = mul(dist, trans[i]);
    bool ok = false;
    for (auto j = (0); j < (4); j++) {
      for (auto k = (0); k < (4); k++) {
        if (d[j][k] <= K) ok = true;
      }
    }
    if (ok) {
      dist = d;
      ans += (1ll << i);
    }
  }
  ans++;
  cout << ans << '\n';
  return 0;
}
