#include <bits/stdc++.h>
using namespace std;
template <typename U, typename V>
inline void smin(U& a, V b) {
  if (a > b) a = b;
}
long long dp[66][4][4];
char t[100010];
int node[100000 * 16][4];
void dfs(int no, int st, int deep = 0) {
  deep++;
  for (int i = 0; i < 4; i++) {
    if (!node[no][i]) {
      smin(dp[0][st][i], deep);
    } else
      dfs(node[no][i], st, deep);
  }
}
int main() {
  long long tar;
  scanf("%I64d%s", &tar, t);
  int trie = 0;
  for (int i = 0, j, k; t[i]; i++) {
    k = 0;
    for (j = 0; j < 15 && t[i + j]; j++) {
      if (!node[k][t[i + j] - 'A']) {
        ++trie;
        node[k][t[i + j] - 'A'] = trie;
      }
      k = node[k][t[i + j] - 'A'];
    }
  }
  memset(dp, 0x3f, sizeof dp);
  for (int i = 0; i < 4; i++) {
    dfs(node[0][i], i);
  }
  for (int i = 1, j, k, m; i < 66; i++) {
    for (j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) {
        for (int l = 0; l < 4; l++) {
          smin(dp[i][j][k], dp[i - 1][j][l] + dp[i - 1][l][k]);
        }
      }
    }
  }
  vector<long long> a(4, 0), b, c(4, 0);
  long long ans = 1;
  for (int i = 66; i--;) {
    b = a;
    long long mn = 0x3f3f3f3f3f3f3f3fll;
    for (int j = 0; j < 4; j++) {
      c[j] = 0x3f3f3f3f3f3f3f3fll;
      for (int k = 0; k < 4; k++) {
        smin(c[j], b[k] + dp[i][j][k]);
      }
      smin(mn, c[j]);
    }
    for (int j = 0; j < 4; j++) b[j] = c[j];
    if (mn < tar) {
      ans += 1ll << i;
      a = b;
    }
  }
  printf("%I64d\n", ans);
  return 0;
}
