#include <bits/stdc++.h>
using namespace std;
struct mat {
  long long v[4][4];
  mat(int tp = 0) {
    if (!tp)
      memset(v, 0, sizeof(v));
    else
      memset(v, 0x3f, sizeof(v));
  }
  mat operator*(const mat &rhs) const {
    mat res = mat(1);
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        for (int k = 0; k < 4; k++)
          res.v[i][j] = min(res.v[i][j], v[i][k] + rhs.v[k][j]);
      }
    }
    return res;
  }
} bs = mat(1);
int nxt[100010 * 20][4], n, rt = 1, cnt = 1;
long long s;
char t[100010];
void dfs(int x, int fst, int dep) {
  for (int i = 0; i < 4; i++) {
    if (!nxt[x][i])
      bs.v[fst][i] = min(bs.v[fst][i], (long long)dep);
    else
      dfs(nxt[x][i], fst, dep + 1);
  }
}
mat pw(mat a, long long b) {
  mat res = mat(0);
  while (b) {
    if (b & 1) res = res * a;
    a = a * a, b >>= 1;
  }
  return res;
}
bool check(long long x) {
  mat res = pw(bs, x);
  long long ans = 1LL << 60;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) ans = min(ans, res.v[i][j]);
  }
  return ans < s;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> s >> t + 1, n = strlen(t + 1);
  for (int i = 1; i <= n; i++) {
    int tmp = rt;
    for (int j = i; j <= min(i + 20, n); j++) {
      if (!nxt[tmp][t[j] - 'A']) nxt[tmp][t[j] - 'A'] = ++cnt;
      tmp = nxt[tmp][t[j] - 'A'];
    }
  }
  for (int i = 0; i < 4; i++) dfs(nxt[rt][i], i, 1);
  long long l = 1, r = 1e18;
  while (l < r) {
    long long mid = l + r >> 1;
    if (check(mid))
      l = mid + 1;
    else
      r = mid;
  }
  if (!check(l)) l--;
  cout << l + 1 << endl;
  return 0;
}
