#include <bits/stdc++.h>
using namespace std;
struct mat {
  long long t[4][4];
  mat operator*(const mat &l) const {
    mat ans = {0};
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        ans.t[i][j] = t[i][0] + l.t[0][j];
        for (int k = 0; k < 4; k++) {
          ans.t[i][j] = min(ans.t[i][j], t[i][k] + l.t[k][j]);
        }
      }
    }
    return ans;
  }
};
char s[100005];
set<int> S;
int DB[300];
long long N, M;
mat ini = {0};
bool chk(long long time) {
  mat ans = {0}, mul = ini;
  while (time > 0) {
    if (time % 2 == 1) ans = ans * mul;
    mul = mul * mul;
    time /= 2;
  }
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      if (ans.t[i][j] < N) return false;
    }
  }
  return true;
}
int main() {
  DB['A'] = 0;
  DB['B'] = 1;
  DB['C'] = 2;
  DB['D'] = 3;
  scanf("%lld%s", &N, s);
  M = strlen(s);
  for (int i = 2; i <= 15; i++) {
    int ad = 0, mul = 1;
    bool ch = false;
    S.clear();
    for (int j = 0; j < i; j++) {
      ad *= 4;
      ad += DB[s[j]];
      mul <<= 2;
    }
    S.insert(ad);
    mul >>= 2;
    for (int j = i; j < M; j++) {
      ad -= mul * DB[s[j - i]];
      ad <<= 2;
      ad += DB[s[j]];
      S.insert(ad);
    }
    S.insert(1 << 2 * i);
    int st = 0;
    for (set<int>::iterator it = S.begin(); it != S.end(); ++it) {
      for (int j = st; j < *it; j++) {
        if (ini.t[j / mul][j % 4] == 0) {
          ini.t[j / mul][j % 4] = i - 1;
        }
      }
      st = *it + 1;
    }
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        if (ini.t[i][j] == 0) ch = true;
      }
    }
    if (!ch) break;
  }
  long long st = 1, en = N, mi, ans = N;
  while (st <= en) {
    mi = (st + en) >> 1;
    if (chk(mi))
      ans = mi, en = mi - 1;
    else
      st = mi + 1;
  }
  printf("%lld", ans);
  return 0;
}
