#include <bits/stdc++.h>
using namespace std;
struct AutomatonNode {
  static const int alphabetSize = 4;
  int length, link, firstPosition, c[alphabetSize];
  bool isCopy;
  AutomatonNode() { memset(c, 255, sizeof(c)); }
};
struct SuffixAutomaton {
  static const char firstSymbol = 'A';
  static const int alphabetSize = 4;
  vector<AutomatonNode> automaton;
  int last, current;
  SuffixAutomaton() : last(0) {
    automaton.emplace_back();
    automaton[last].link = -1;
    automaton[last].length = 0;
  }
  SuffixAutomaton(int n) : SuffixAutomaton() { automaton.reserve(n); }
  void add(char c) {
    automaton.emplace_back();
    current = automaton.size() - 1;
    automaton[current].length = automaton[last].length + 1;
    automaton[current].firstPosition = automaton[last].length;
    int it = last, currentChar = c - firstSymbol;
    while (it != -1) {
      if (automaton[it].c[currentChar] == -1) {
        automaton[it].c[currentChar] = current;
        it = automaton[it].link;
      } else
        break;
    }
    if (it == -1)
      automaton[current].link = 0;
    else {
      int next = automaton[it].c[currentChar];
      if (automaton[it].length + 1 == automaton[next].length)
        automaton[current].link = next;
      else {
        automaton.emplace_back();
        int nextCopy = automaton.size() - 1;
        copy(automaton[next].c, automaton[next].c + alphabetSize,
             automaton[nextCopy].c);
        automaton[nextCopy].length = automaton[it].length + 1;
        automaton[nextCopy].firstPosition = automaton[next].firstPosition;
        automaton[nextCopy].link = automaton[next].link;
        automaton[next].link = automaton[current].link = nextCopy;
        automaton[nextCopy].isCopy = true;
        while (it != -1 && automaton[it].c[currentChar] == next) {
          automaton[it].c[currentChar] = nextCopy;
          it = automaton[it].link;
        }
      }
    }
    last = current;
  }
  SuffixAutomaton(string& S) : SuffixAutomaton(S.size() * 2) {
    for (auto c : S) add(c);
  }
  size_t size() { return automaton.size(); }
  AutomatonNode& operator[](int n) { return automaton[n]; }
  vector<AutomatonNode>::iterator begin() { return automaton.begin(); }
  vector<AutomatonNode>::iterator end() { return automaton.end(); }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  long long n, INF = numeric_limits<long long>::max() / 2;
  int logN = 1;
  string s;
  cin >> n >> s;
  SuffixAutomaton sSuffixAutomaton(s);
  while ((1ll << logN) < n) logN++;
  vector<vector<vector<long long>>> DP(
      4, vector<vector<long long>>(4, vector<long long>(logN, INF)));
  for (size_t i = 1; i < sSuffixAutomaton.size(); i++) {
    int c = s[sSuffixAutomaton[i].firstPosition -
              sSuffixAutomaton[sSuffixAutomaton[i].link].length] -
            'A';
    for (int j = 0; j < 4; j++)
      if (sSuffixAutomaton[i].c[j] == -1)
        DP[c][j][0] = min(
            DP[c][j][0],
            (long long)sSuffixAutomaton[sSuffixAutomaton[i].link].length + 2);
  }
  for (int z = 1; z < logN; z++)
    for (int k = 0; k < 4; k++)
      for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
          DP[i][j][z] = min(DP[i][j][z], DP[i][k][z - 1] + DP[k][j][z - 1] - 1);
  long long L = 0, R = INF;
  while (R - L > 1) {
    long long M = (L + R) / 2;
    vector<long long> minDist(4, 0);
    for (int i = 0; i < logN; i++)
      if (M & (1ll << i)) {
        vector<long long> dist(4, INF);
        for (int j = 0; j < 4; j++)
          for (int k = 0; k < 4; k++)
            dist[j] = min(dist[j], DP[j][k][i] + minDist[k] - 1);
        for (int j = 0; j < 4; j++) minDist[j] = dist[j];
      }
    if (*min_element(minDist.begin(), minDist.end()) < n)
      L = M;
    else
      R = M;
  }
  cout << L + 1;
  return 0;
}
