#include <bits/stdc++.h>
using namespace std;
const int inf = int(1e9);
const double pi = 4 * atan(double(1.0));
const double eps = 1e-9;
const int N = int(1e5) + 100;
struct node {
  int len, _link;
  int _next[4];
};
int sz, last;
long long len;
node v[2 * N];
bool used[2 * N];
long long d[2 * N][4];
long long can[10][10];
char s[N];
vector<pair<int, int> > g[2 * N];
inline void init() {
  sz = last = 0;
  v[0].len = 0;
  v[0]._link = -1;
  for (int i = 0; i < 4; ++i) {
    v[0]._next[i] = -1;
  }
}
inline void add(int c) {
  int nlast = ++sz;
  v[nlast].len = v[last].len + 1;
  for (int i = 0; i < 4; ++i) {
    v[nlast]._next[i] = -1;
  }
  int p = last;
  while (p != -1 && v[p]._next[c] == -1) {
    v[p]._next[c] = nlast;
    p = v[p]._link;
  }
  if (p == -1) {
    v[nlast]._link = 0;
  } else {
    int q = v[p]._next[c];
    if (v[p].len + 1 == v[q].len) {
      v[nlast]._link = q;
    } else {
      int clone = ++sz;
      for (int i = 0; i < 4; ++i) {
        v[clone]._next[i] = v[q]._next[i];
      }
      v[clone]._link = v[q]._link;
      v[clone].len = v[p].len + 1;
      while (p != -1 && v[p]._next[c] == q) {
        v[p]._next[c] = clone;
        p = v[p]._link;
      }
      v[nlast]._link = v[q]._link = clone;
    }
  }
  last = nlast;
}
void calc(int v) {
  if (used[v]) {
    return;
  }
  used[v] = true;
  for (int i = 0; i < 4; ++i) {
    d[v][i] = len + 10;
  }
  for (int i = 0; i < int((g[v]).size()); ++i) {
    if (g[v][i].first == 0) {
      d[v][g[v][i].second] = min(d[v][g[v][i].second], 1LL);
    } else {
      calc(g[v][i].first);
      for (int j = 0; j < 4; ++j) {
        d[v][j] = min(d[v][j], d[g[v][i].first][j] + 1);
      }
    }
  }
}
long long mat[10][10], tmp[10][10];
void calc_mat(long long step) {
  if (step == 1) {
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        mat[i][j] = can[i][j];
      }
    }
    return;
  }
  if (step % 2 == 0) {
    calc_mat(step / 2);
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        tmp[i][j] = len + 10;
        for (int z = 0; z < 4; ++z) {
          tmp[i][j] = min(tmp[i][j], mat[i][z] + mat[z][j]);
        }
      }
    }
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        mat[i][j] = tmp[i][j];
      }
    }
    return;
  }
  calc_mat(step - 1);
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      tmp[i][j] = len + 10;
      for (int z = 0; z < 4; ++z) {
        tmp[i][j] = min(tmp[i][j], mat[i][z] + can[z][j]);
      }
    }
  }
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      mat[i][j] = tmp[i][j];
    }
  }
}
int main() {
  scanf("%lld", &len);
  scanf("%s", s);
  int n = (int)strlen(s);
  init();
  for (int i = 0; i < n; ++i) {
    add(s[i] - 'A');
  }
  for (int i = 0; i <= sz; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (v[i]._next[j] != -1) {
        g[v[i]._next[j]].push_back(make_pair(i, j));
      }
    }
  }
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      can[i][j] = len + 10;
    }
  }
  for (int i = 1; i <= sz; ++i) {
    calc(i);
    for (int j = 0; j < 4; ++j) {
      if (v[i]._next[j] == -1) {
        for (int z = 0; z < 4; ++z) {
          can[z][j] = min(can[z][j], 1LL * d[i][z]);
        }
      }
    }
  }
  long long ans = 1, l = 2, r = len;
  while (l <= r) {
    long long mid = (l + r) / 2;
    calc_mat(mid - 1);
    bool fl = false;
    for (int i = 0; i < 4 && !fl; ++i) {
      for (int j = 0; j < 4; ++j) {
        if (mat[i][j] < len) {
          fl = true;
          break;
        }
      }
    }
    if (fl) {
      ans = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << ans << endl;
  return 0;
}
