#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 7;
const long long inf = 9e18 + 7;
int res[N], ch[5][5];
long long n, m;
char s[N], fl[N];
struct matrix {
  long long ch[4][4];
} t;
inline matrix mul(matrix a, matrix b) {
  matrix c;
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) {
      c.ch[i][j] = inf;
      for (int k = 0; k <= 3; k++)
        c.ch[i][j] = min(c.ch[i][j], a.ch[i][k] + b.ch[k][j]);
    }
  return c;
}
inline long long check(long long u) {
  matrix a, b;
  bool fl = false;
  long long v = u;
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) b.ch[i][j] = ch[i + 1][j + 1];
  while (u > 0) {
    if (u & 1) {
      if (!fl)
        fl = true, a = b;
      else
        a = mul(a, b);
    }
    u = u >> 1, b = mul(b, b);
  }
  long long t = inf;
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 3; j++) t = min(t, a.ch[i][j]);
  return t + v + 1;
}
int main() {
  scanf("%lld%s", &n, s + 1), m = strlen(s + 1), res[0] = 1;
  for (int i = 1; i <= 10; i++) res[i] = res[i - 1] * 4;
  for (char i = 'A'; i <= 'D'; i++)
    for (char j = 'A'; j <= 'D'; j++) {
      memset(fl, 0, sizeof(fl));
      bool opv = false;
      for (int z = 0; z <= 9; z++) {
        int cnt = 0;
        for (int x = 1; x <= m - 2 - z; x++) {
          if (s[x] == i && s[x + 1 + z] == j) {
            int opt = 0;
            for (int t = 1; t <= z; t++) opt = opt * 4 + s[x + t] - 'A' + 1;
            if (!fl[opt]) fl[opt] = 1, cnt++;
          }
        }
        if (cnt != res[z]) {
          ch[i - 'A' + 1][j - 'A' + 1] = z, opv = true;
          break;
        }
      }
      if (!opv) ch[i - 'A' + 1][j - 'A' + 1] = 10;
    }
  long long l = 0, r = n, ans;
  while (l <= r) {
    long long d = (l + r) / 2;
    if (check(d) <= n)
      ans = d, l = d + 1;
    else
      r = d - 1;
  }
  cout << ans + 1 << endl;
  return 0;
}
