#include <bits/stdc++.h>
using namespace std;
const int N = 234567;
const int inf = 1e9;
const long long llinf = 9e18;
char s[N];
int sz;
int mx[N], suf[N];
int go[N][4];
int f[N][4];
int cost[4][4];
struct matrix {
  long long a[4][4];
  matrix() {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        a[i][j] = llinf;
      }
    }
  };
};
matrix operator*(const matrix& a, const matrix& b) {
  matrix c = matrix();
  for (int k = 0; k < 4; k++) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
      }
    }
  }
  return c;
}
matrix power(matrix a, long long step) {
  matrix res;
  for (int i = 0; i < 4; i++) {
    res.a[i][i] = 0;
  }
  while (step > 0) {
    if (step & 1) {
      res = res * a;
    }
    a = a * a;
    step >>= 1;
  }
  return res;
}
int append(int p, int c) {
  int np = sz++;
  mx[np] = mx[p] + 1;
  while (p != -1 && go[p][c] == 0) {
    go[p][c] = np;
    p = suf[p];
  }
  if (p == -1) {
    suf[np] = 0;
  } else {
    int q = go[p][c];
    if (mx[q] == mx[p] + 1) {
      suf[np] = q;
    } else {
      int nq = sz++;
      mx[nq] = mx[p] + 1;
      suf[nq] = suf[q];
      suf[q] = suf[np] = nq;
      for (int c = 0; c < 4; c++) {
        go[nq][c] = go[q][c];
      }
      while (p != -1 && go[p][c] == q) {
        go[p][c] = nq;
        p = suf[p];
      }
    }
  }
  return np;
}
void Solve(int v) {
  if (f[v][0] < inf) {
    return;
  }
  for (int c = 0; c < 4; c++) {
    int u = go[v][c];
    if (u == 0) {
      f[v][c] = 0;
    } else {
      Solve(u);
      for (int d = 0; d < 4; d++) {
        f[v][d] = min(f[v][d], f[u][d] + 1);
      }
    }
  }
}
int main() {
  long long m;
  scanf("%lld", &m);
  scanf("%s", s);
  int n = strlen(s);
  sz = 1;
  int p = 0;
  suf[0] = -1;
  for (int i = 0; i < n; i++) {
    p = append(p, s[i] - 'A');
  }
  for (int c = 0; c < 4; c++) {
    for (int i = 0; i < sz; i++) {
      for (int d = 0; d < 4; d++) {
        f[i][d] = inf;
      }
    }
    Solve(go[0][c]);
    for (int d = 0; d < 4; d++) {
      cost[c][d] = f[go[0][c]][d] + 1;
    }
  }
  matrix base;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      base.a[i][j] = cost[i][j];
    }
  }
  long long low = 1;
  long long high = (long long)1e18 + 10;
  while (high - low > 1) {
    long long mid = (low + high) >> 1;
    matrix res = power(base, mid - 1);
    long long mn = llinf;
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        mn = min(mn, res.a[i][j]);
      }
    }
    if (mn + 1 <= m) {
      low = mid;
    } else {
      high = mid;
    }
  }
  printf("%lld\n", low);
  return 0;
}
