#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T1, typename T2>
inline void chkmin(T1& x, const T2& y) {
  if (y < x) x = y;
}
template <typename T1, typename T2>
inline void chkmax(T1& x, const T2& y) {
  if (x < y) x = y;
}
ll len;
string t;
ll n;
const ll N = 1e5 + 10;
const ll A = 4;
const ll BUBEN_LEN = 10;
ll minWord[A][A];
vector<string> have[BUBEN_LEN];
void relax(const string& s) {
  if (s.size() < 2) return;
  if (binary_search((have[s.size() - 1]).begin(), (have[s.size() - 1]).end(),
                    s))
    return;
  if (!binary_search((have[s.size() - 2]).begin(), (have[s.size() - 2]).end(),
                     s.substr(0, s.size() - 1)))
    return;
  chkmin(minWord[s[0] - 'A'][s.back() - 'A'], s.size());
}
void rec(string& s) {
  relax(s);
  if (s.size() == BUBEN_LEN) return;
  s += 'A';
  for (ll i = 0; i < A; ++i) {
    rec(s);
    s[s.size() - 1]++;
  }
  s.pop_back();
}
ll dp[N][A][A];
ll fans[N][A];
void precalc() {
  for (ll i = 0; i < A; ++i) {
    for (ll j = 0; j < A; ++j) {
      minWord[i][j] = N;
    }
  }
  for (ll i = 0; i < n; ++i) {
    string now = "";
    for (ll j = 0; i + j < n && j < BUBEN_LEN; ++j) {
      now += t[i + j];
      have[j].push_back(now);
    }
  }
  for (ll i = 0; i < BUBEN_LEN; ++i) {
    sort((have[i]).begin(), (have[i]).end());
    have[i].resize(unique((have[i]).begin(), (have[i]).end()) -
                   have[i].begin());
  }
  string s;
  rec(s);
  for (ll i = 0; i < N; ++i) {
    for (ll j = 0; j < A; ++j) {
      for (ll k = 0; k < A; ++k) {
        dp[i][j][k] = -1;
      }
    }
  }
  for (ll first = 0; first < A; ++first) {
    for (ll last = 0; last < A; ++last) {
      dp[minWord[first][last] - 1][first][last] = 1;
    }
  }
  for (ll len = 0; len < N; ++len) {
    for (ll begin = 0; begin < A; ++begin) {
      for (ll first = 0; first < A; ++first) {
        if (dp[len][begin][first] == -1) continue;
        for (ll last = 0; last < A; ++last) {
          ll nxtLen = len + minWord[first][last] - 1;
          if (nxtLen >= N) continue;
          chkmax(dp[nxtLen][begin][last], dp[len][begin][first] + 1);
        }
      }
    }
  }
  for (ll i = 0; i < A; ++i) {
    for (ll j = 0; j < A; ++j) {
      dp[0][i][j] = 0;
    }
  }
  for (ll len = 0; len < N; ++len) {
    for (ll begin = 0; begin < A; ++begin) {
      for (ll end = 0; end < A; ++end) {
        chkmax(fans[len][begin], dp[len][begin][end]);
        for (ll last = 0; last < A; ++last) {
          ll nxtLen = len + minWord[end][last] - 1;
          if (nxtLen >= N) continue;
          for (ll j = len + 1; j <= nxtLen; ++j) {
            chkmax(fans[j][begin], dp[len][begin][end] + 1);
          }
        }
      }
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout.precision(20), cout.setf(ios::fixed);
  cin >> len >> t;
  n = t.size();
  precalc();
  if (len < N) {
    ll ans = 0;
    for (ll i = 0; i < A; ++i) {
      chkmax(ans, fans[len][i]);
    }
    cout << ans << endl;
  } else {
    ll ans = 0;
    for (ll cycleLen = 1; cycleLen < N; ++cycleLen) {
      for (ll begin = 0; begin < A; ++begin) {
        ll cnt = len / cycleLen;
        ll pref = len % cycleLen;
        ll myFans = dp[cycleLen][begin][begin] * cnt;
        for (ll other = 0; other < A; ++other) {
          ll frelax = myFans + fans[pref][begin];
          chkmax(ans, frelax);
          frelax = myFans + dp[pref][other][begin];
          chkmax(ans, frelax);
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}
