#include <bits/stdc++.h>
using namespace std;
string t;
int tlen;
const long long int INF = 1ll << 62;
void print(long long int** A, int N, int M) {
  return;
  cout << "================\n";
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cout << (A[i][j] < 0 ? -1 : A[i][j]) << " ";
    }
    cout << endl;
  }
}
void matMult(long long int** A, long long int** B, long long int** C, int N,
             int K, int M) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      long long int ans = -INF;
      for (int k = 0; k < K; k++) ans = max(ans, A[i][k] + B[k][j]);
      C[i][j] = ans < -INF ? -INF : ans;
    }
  }
}
void assignment(long long int** A, long long int** B, int N, int M) {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++) A[i][j] = B[i][j];
}
void matexp(long long int** A, long long int** res, long long int** temp, int N,
            long long int pow) {
  if (pow == 0) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++) res[i][j] = -INF;
    for (int i = 0; i < N; i++) res[i][i] = 0;
    return;
  }
  matexp(A, res, temp, N, pow / 2);
  matMult(res, res, temp, N, N, N);
  if (pow % 2)
    matMult(A, temp, res, N, N, N);
  else
    assignment(res, temp, N, N);
}
int find(char A, char B) {
  int len = 1;
  while (len++) {
    set<string> stringMap;
    for (int i = 0; i < tlen - len + 1; i++)
      if (t[i] == A && t[i + len - 1] == B) stringMap.insert(t.substr(i, len));
    int n = stringMap.size();
    if (n < (1ll << (2 * (len - 2)))) {
      return len;
    }
  }
}
int main() {
  long long int N;
  cin >> N;
  cin >> t;
  tlen = t.length();
  int alpValues[4][4];
  int minAlpha[4] = {20, 20, 20, 20};
  int maxAlpha = -1;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      alpValues[i][j] = find(i + 'A', j + 'A');
      maxAlpha = max(maxAlpha, alpValues[i][j]);
      minAlpha[i] = min(minAlpha[i], alpValues[i][j]);
    }
  }
  int matSize = 4 * (maxAlpha - 1);
  long long int** mat = new long long int*[matSize];
  long long int** res = new long long int*[matSize];
  long long int** temp = new long long int*[matSize];
  for (int i = 0; i < matSize; i++) {
    mat[i] = new long long int[matSize];
    res[i] = new long long int[matSize];
    temp[i] = new long long int[matSize];
    fill_n(mat[i], matSize, -INF);
  }
  for (int i = 0; i < 4; i++) {
    for (int k = 0; k < 4; k++) {
      mat[i][(alpValues[i][k] - 2) * 4 + k] = 1;
    }
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 1; j < maxAlpha - 1; j++) {
      mat[j * 4 + i][(j - 1) * 4 + i] = 0;
    }
  }
  long long int** base = new long long int*[matSize];
  long long int** ans = new long long int*[matSize];
  for (int i = 0; i < matSize; i++) {
    base[i] = new long long int[1];
    base[i][0] = 0;
    ans[i] = new long long int[1];
  }
  matexp(mat, res, temp, matSize, N);
  print(res, matSize, matSize);
  print(base, matSize, 1);
  matMult(res, base, ans, matSize, matSize, 1);
  print(ans, matSize, 1);
  cout << max(ans[0][0], max(ans[1][0], max(ans[2][0], ans[3][0]))) << endl;
  return 0;
}
