#include <bits/stdc++.h>
using namespace std;
const int MAXLEN = 100000;
long long have;
char s[MAXLEN + 1];
int slen;
typedef struct Node {
  int start, end;
  int childs[4];
  int suffix;
  Node(int start, int end) : start(start), end(end) {
    memset(childs, -1, sizeof(childs));
    suffix = -1;
  }
} Node;
vector<Node> nodes;
int addnode(int start, int end) {
  nodes.push_back(Node(start, end));
  return ((int)(nodes).size()) - 1;
}
int create() {
  int root = addnode(0, 0);
  int atnode = root, atedge = 0, atlen = 0, rem = 0, prev = -1;
  for (int i = 0; i < slen; ++i) {
    ++rem;
    prev = -1;
    while (rem > 0) {
      int tonode = nodes[atnode].childs[s[atedge] - 'A'];
      int tostart = tonode == -1 ? -1 : nodes[tonode].start;
      if (tonode != -1 && nodes[tonode].start + atlen >= nodes[tonode].end) {
        atedge += nodes[tonode].end - nodes[tonode].start;
        atlen -= nodes[tonode].end - nodes[tonode].start;
        atnode = tonode;
        continue;
      }
      if (tonode == -1) {
        int leaf = addnode(i, slen);
        nodes[atnode].childs[s[atedge] - 'A'] = leaf;
        if (prev != -1) nodes[prev].suffix = atnode;
        prev = atnode;
      } else if (s[tostart + atlen] == s[i]) {
        ++atlen;
        if (prev != -1) nodes[prev].suffix = atnode;
        prev = atnode;
        break;
      } else {
        int branch = addnode(tostart, tostart + atlen);
        nodes[tonode].start += atlen;
        int leaf = addnode(i, slen);
        nodes[atnode].childs[s[atedge] - 'A'] = branch;
        nodes[branch].childs[s[tostart + atlen] - 'A'] = tonode;
        nodes[branch].childs[s[i] - 'A'] = leaf;
        if (prev != -1) nodes[prev].suffix = branch;
        prev = branch;
      }
      --rem;
      if (atnode == root) {
        if (atlen > 0) --atlen;
        atedge++;
      } else {
        atnode = nodes[atnode].suffix;
      }
    }
  }
  return root;
}
void print(int node, int depth) {
  for (int i = 0; i < depth; ++i) printf("  ");
  printf("'");
  for (int i = nodes[node].start; i < nodes[node].end; ++i) printf("%c", s[i]);
  printf("'");
  printf(" -> %d", node);
  if (nodes[node].suffix != -1) printf(" [%d]", nodes[node].suffix);
  puts("");
  for (int i = 0; i < 4; ++i)
    if (nodes[node].childs[i] != -1) print(nodes[node].childs[i], depth + 1);
}
int cst[4][4];
int bst[5][4][4];
void update(int a, int b, int cur) {
  if (cur < cst[a][b]) cst[a][b] = cur;
}
void dfs(int node, int a, int len) {
  int clen = nodes[node].end - nodes[node].start;
  if (clen > 1) {
    int x = s[nodes[node].start + 1] - 'A';
    for (int b = (0); b < (4); ++b) update(a, b, len + 2 + (b == x ? 1 : 0));
  } else
    for (int i = (0); i < (4); ++i) {
      if (nodes[node].childs[i] != -1)
        dfs(nodes[node].childs[i], a, len + 1);
      else
        for (int b = (0); b < (4); ++b)
          update(a, b, len + 2 + (b != i ? 1 : 0));
    }
}
void run() {
  scanf("%I64d%s", &have, s);
  slen = strlen(s);
  for (int i = (0); i < (4); ++i)
    for (int j = (0); j < (4); ++j) cst[i][j] = INT_MAX;
  int root = create();
  for (int i = (0); i < (4); ++i) dfs(nodes[root].childs[i], i, 0);
  for (int i = (0); i < (4); ++i)
    for (int j = (0); j < (4); ++j) bst[1][i][j] = cst[i][j];
  for (int len = (2); len <= (4); ++len)
    for (int i = (0); i < (4); ++i)
      for (int j = (0); j < (4); ++j) {
        bst[len][i][j] = INT_MAX;
        for (int k = (0); k < (4); ++k)
          if (bst[len - 1][i][k] + cst[k][j] - 1 < bst[len][i][j])
            bst[len][i][j] = bst[len - 1][i][k] + cst[k][j] - 1;
      }
  long long ret = 1;
  for (int i = (0); i < (4); ++i)
    for (int j = (0); j < (4); ++j)
      for (int k = (0); k < (4); ++k)
        for (int cyc = (1); cyc <= (4); ++cyc)
          for (int pre = (i == j ? 0 : 1); pre < (cyc); ++pre)
            for (int suf = (j == k ? 0 : 1); suf < (cyc); ++suf) {
              long long rem = have - 1;
              if (pre > 0) rem -= bst[pre][i][j] - 1;
              if (suf > 0) rem -= bst[suf][j][k] - 1;
              if (rem < 0) continue;
              long long times = rem / (bst[cyc][j][j] - 1);
              long long cur = pre + times * cyc + suf + 1;
              if (cur > ret) ret = cur;
            }
  printf("%I64d\n", ret);
}
int main() {
  run();
  return 0;
}
