#include <bits/stdc++.h>
using namespace std;
long long m, xzq, mn;
int i, n, ii, j, k, root, lim, lm, tot;
bool pp;
long long two[63];
int fr[15];
long long a[5][5][64];
long long b[5][5], c[5][5];
char s[100011];
int trie[1000111][5];
void Read() {
  char c;
  while (c = getchar(), c < 'A' || c > 'D')
    ;
  s[++n] = c;
  while (c = getchar(), c >= 'A' && c <= 'D') s[++n] = c;
}
void add(int st, int len) {
  int x, i, y;
  x = root;
  for (i = st; i <= st + len - 1; i++) {
    y = s[i] - 64;
    if (trie[x][y] == 0) trie[x][y] = ++tot;
    x = trie[x][y];
  }
}
void dfs(int i, int j, int x, int len) {
  int k;
  if (trie[x][j] == 0) {
    if (len < a[i][j][0]) a[i][j][0] = len;
    return;
  }
  if (len >= a[i][j][0]) return;
  for (k = 1; k <= 4; k++)
    if (trie[x][k] != 0) dfs(i, j, trie[x][k], len + 1);
}
int main() {
  scanf("%I64d", &m);
  Read();
  root = 1;
  tot = 1;
  fr[0] = 1;
  for (i = 1; i <= n; i++) {
    fr[i] = fr[i - 1] * 4;
    if (fr[i] >= n - i + 1) break;
  }
  lim = i;
  for (i = 1; i <= n; i++) {
    add(i, min(n - i + 1, lim));
  }
  for (i = 1; i <= 4; i++)
    for (j = 1; j <= 4; j++)
      if (trie[root][i] && trie[root][j]) a[i][j][0] = 2147483647;
  for (i = 1; i <= 4; i++)
    for (j = 1; j <= 4; j++) {
      if (trie[root][i] && trie[root][j]) dfs(i, j, trie[root][i], 1);
    }
  two[0] = 1;
  for (ii = 1; ii <= 2147483647; ii++) {
    two[ii] = two[ii - 1] * 2;
    if (two[ii] > m) break;
    for (i = 1; i <= 4; i++)
      for (j = 1; j <= 4; j++)
        for (k = 1; k <= 4; k++)
          if (trie[root][i] && trie[root][j] && trie[root][k]) {
            if (a[i][j][ii] == 0 ||
                a[i][k][ii - 1] + a[k][j][ii - 1] < a[i][j][ii])
              a[i][j][ii] = a[i][k][ii - 1] + a[k][j][ii - 1];
          }
  }
  lm = ii - 1;
  pp = false;
  for (ii = lm; ii >= 0; ii--) {
    mn = m + m;
    if (pp == false) {
      for (i = 1; i <= 4; i++)
        for (j = 1; j <= 4; j++)
          if (trie[root][i] && trie[root][j]) {
            if (a[i][j][ii] < mn) mn = a[i][j][ii];
          }
      if (mn < m) {
        pp = true;
        for (i = 1; i <= 4; i++)
          for (j = 1; j <= 4; j++) b[i][j] = a[i][j][ii];
        xzq += two[ii];
      }
    } else {
      for (i = 1; i <= 4; i++)
        for (j = 1; j <= 4; j++) {
          c[i][j] = 0;
          for (k = 1; k <= 4; k++)
            if (trie[root][i] && trie[root][j] && trie[root][k])
              if (c[i][j] == 0 || b[i][k] + a[k][j][ii] < c[i][j])
                c[i][j] = b[i][k] + a[k][j][ii];
          if (trie[root][i] && trie[root][j])
            if (c[i][j] < mn) mn = c[i][j];
        }
      if (mn < m) {
        xzq += two[ii];
        for (i = 1; i <= 4; i++)
          for (j = 1; j <= 4; j++) b[i][j] = c[i][j];
      }
    }
  }
  xzq++;
  printf("%I64d\n", xzq);
}
