#include <bits/stdc++.h>
using namespace std;
const long long INF = 2e18;
long long n;
string S;
set<string> M;
const int N = 4;
const int P = 64;
int m;
struct mat {
  long long d[N][N];
} F, G[P], H;
long long res;
mat operator*(mat a, mat b) {
  mat c;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) c.d[i][j] = INF;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j)
      for (int k = 0; k < 4; ++k)
        c.d[j][k] = min(c.d[j][k], a.d[j][i] + b.d[i][k]);
  return c;
}
void dfs(string S) {
  for (char i = 'A'; i <= 'D'; ++i) {
    string T = S + i;
    if (M.count(T))
      dfs(T);
    else
      F.d[T[0] - 'A'][i - 'A'] =
          min(F.d[T[0] - 'A'][i - 'A'], (long long)T.size() - 1);
  }
}
int main() {
  cin >> n >> S;
  m = S.size();
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) F.d[i][j] = H.d[i][j] = INF;
  for (int i = 0; i < 4; ++i) H.d[i][i] = 0;
  for (int i = 0; i < m; ++i)
    for (int j = 1; j <= 10 && i + j <= m; ++j) M.insert(S.substr(i, j));
  dfs("");
  G[0] = F;
  for (int i = 1; i < P; ++i) G[i] = G[i - 1] * G[i - 1];
  for (int i = P - 1; ~i; --i) {
    mat c;
    c = H * G[i];
    int flag = 0;
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j)
        if (c.d[i][j] < n) flag = 1;
    if (flag) H = c, res += 1ll << i;
  }
  cout << res + 1 << endl;
}
