#include <bits/stdc++.h>
using namespace std;
string t;
long long n, best[4][4], canget[4][4][1 << 18];
long long dp[4][4][65];
long long calc[4][4];
long long calc2[4][4];
void compute(int i, int j, int k) {
  dp[i][j][k] = 1e18 + 10;
  for (int l = 0; l < 4; ++l)
    dp[i][j][k] = min(dp[i][l][k - 1] + dp[l][j][k - 1], dp[i][j][k]);
}
void computemindist(long long x) {
  if (x == 0) {
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j) calc[i][j] = 0;
    return;
  }
  long long maxi = 0;
  long long x1 = x;
  while (x1 != 1) {
    x1 /= 2;
    ++maxi;
  }
  long long k = (1LL) << maxi;
  computemindist(x - k);
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) calc2[i][j] = 1e18 + 10;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k)
        calc2[i][j] = min(calc2[i][j], dp[i][k][maxi] + calc[k][j]);
    }
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) calc[i][j] = calc2[i][j];
}
int main() {
  cin >> n >> t;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) best[i][j] = -1;
  for (int i = 0; i <= 9; ++i) {
    if (t.length() < i + 2) break;
    for (int a = 0; a < 4; ++a)
      for (int b = 0; b < 4; ++b) {
        for (int c = 0; c < 1 << 18; ++c) canget[a][b][c] = 0;
      }
    int x = 0;
    for (int j = 0; j < i; ++j) {
      x *= 4;
      x += t[j] - 'A';
    }
    for (int j = 1; j < t.length() - i; ++j) {
      if (i == 0) {
        x = 0;
      } else {
        x -= (t[j - 1] - 'A') * (1 << (2 * i - 2));
        x *= 4;
        x += t[j + i - 1] - 'A';
      }
      canget[t[j - 1] - 'A'][t[j + i] - 'A'][x] = 1;
    }
    for (int k = 0; k < 4; ++k)
      for (int j = 0; j < 4; ++j) {
        for (int c = 0; c < 1 << (2 * i); ++c) {
          if (canget[k][j][c] == 0 && best[k][j] == -1) best[k][j] = i + 1;
        }
      }
  }
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j) dp[i][j][0] = best[i][j];
  for (int i = 1; i < 60; ++i) {
    for (int j = 0; j < 4; ++j)
      for (int k = 0; k < 4; ++k) compute(j, k, i);
  }
  long long lo = 1, hi = 1e18;
  while (lo != hi) {
    long long mid = (lo + hi) / 2;
    bool y1 = false;
    computemindist(mid);
    for (int i = 0; i < 4; ++i)
      for (int j = 0; j < 4; ++j) {
        if (calc[i][j] < n) y1 = true;
      }
    if (y1)
      lo = mid + 1;
    else
      hi = mid;
  }
  cout << lo << endl;
}
