#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int ch[N * 12][4], nd = 1, m;
char s[N];
long long T;
struct Mat {
  long long a[4][4];
  Mat() { memset(a, 50, sizeof(a)); }
  Mat operator*(const Mat &b) const {
    Mat ans;
    for (int i = (int)(0); i <= (int)(3); i++)
      for (int j = (int)(0); j <= (int)(3); j++)
        for (int k = (int)(0); k <= (int)(3); k++)
          ans.a[i][j] = min(ans.a[i][j], a[i][k] + b.a[k][j]);
    return ans;
  }
} tr, bas, P[65];
void dfs(int x, int c1, int l) {
  for (int i = (int)(0); i <= (int)(3); i++)
    if (!ch[x][i])
      tr.a[c1][i] = min(tr.a[c1][i], 1ll * l - 1);
    else
      dfs(ch[x][i], l == 1 ? i : c1, l + 1);
}
int main() {
  scanf("%lld", &T);
  scanf("%s", s + 1);
  m = strlen(s + 1);
  for (int i = (int)(1); i <= (int)(m); i++) {
    int p = i, l = 1, x = 1;
    for (; l <= 11 && p <= m;) {
      int c = s[p] - 'A';
      if (!ch[x][c]) ch[x][c] = ++nd;
      x = ch[x][c];
      ++l;
      ++p;
    }
  }
  memset(tr.a, 50, sizeof(tr.a));
  dfs(1, -1, 1);
  P[0] = tr;
  for (int i = (int)(1); i <= (int)(60); i++) P[i] = P[i - 1] * P[i - 1];
  for (int i = (int)(0); i <= (int)(3); i++) bas.a[i][i] = 0;
  long long ans = 0;
  for (int i = (int)(60); i >= (int)(0); i--) {
    Mat tmp = bas * P[i];
    bool flg = 0;
    for (int j = (int)(0); j <= (int)(3); j++)
      for (int k = (int)(0); k <= (int)(3); k++) flg |= (tmp.a[j][k] < T);
    if (flg) bas = tmp, ans += (1ll << i);
  }
  printf("%lld\n", ans + 1);
}
