#include <bits/stdc++.h>
using namespace std;
const int MAXL = 100500;
const int MAXV = 20 * MAXL;
int root = 1, ind = 1;
int to[MAXV][4];
char t[MAXL];
int tlen;
long long n;
int min_lost_len[4][4];
int used[4];
int len[4];
const int MAXD = 60;
long long val[MAXD][4][4];
void add(char *s, int all_len) {
  int cur_v = root;
  for (int i = 0; i < all_len && s[i]; ++i) {
    if (to[cur_v][s[i] - 'A'] == 0) {
      ++ind;
      to[cur_v][s[i] - 'A'] = ind;
    }
    cur_v = to[cur_v][s[i] - 'A'];
  }
}
int get_depth(int v, int symb) {
  if (v == 0 || to[v][symb] == 0) {
    return 0;
  }
  auto tmp_arr = {get_depth(to[v][0], symb), get_depth(to[v][1], symb),
                  get_depth(to[v][2], symb), get_depth(to[v][3], symb)};
  return *min_element(tmp_arr.begin(), tmp_arr.end()) + 1;
}
bool can_get_len(long long el_time, long long len) {
  long long res_val[4][4] = {};
  long long tmp_val[4][4];
  for (int bit = MAXD - 1; bit >= 0; --bit) {
    if (el_time & (1ll << bit)) {
      for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
          long long &res = tmp_val[i][j] = -1ll;
          for (int k = 0; k < 4; ++k) {
            long long cur_val = res_val[i][k] + val[bit][k][j];
            if (res == -1 || res > cur_val) {
              res = cur_val;
            }
          }
        }
      }
      for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
          res_val[i][j] = tmp_val[i][j];
        }
      }
    }
    long long min_val = len;
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        min_val = min(min_val, res_val[i][j]);
      }
    }
    if (min_val >= len) {
      return true;
    }
  }
  return false;
}
int main() {
  scanf("%lld %s", &n, t);
  tlen = strlen(t);
  for (int i = 0; i < tlen; ++i) {
    add(t + i, 11);
  }
  for (int start_symb = 0; start_symb < 4; ++start_symb) {
    for (int end_symb = 0; end_symb < 4; ++end_symb) {
      val[0][start_symb][end_symb] =
          get_depth(to[root][start_symb], end_symb) + 1;
    }
  }
  for (int level = 1; level < MAXD; ++level) {
    for (int start_symb = 0; start_symb < 4; ++start_symb) {
      for (int end_symb = 0; end_symb < 4; ++end_symb) {
        long long &res = val[level][start_symb][end_symb];
        res = -1ll;
        for (int inter_symb = 0; inter_symb < 4; ++inter_symb) {
          long long cur_val = val[level - 1][start_symb][inter_symb] +
                              val[level - 1][inter_symb][end_symb];
          if (res == -1ll || res > cur_val) {
            res = cur_val;
          }
        }
      }
    }
  }
  long long l_bord = 0, r_bord = n + 1;
  while (l_bord < r_bord - 1) {
    long long m_bord = (l_bord + r_bord) / 2;
    if (can_get_len(m_bord, n)) {
      r_bord = m_bord;
    } else {
      l_bord = m_bord;
    }
  }
  cout << r_bord << '\n';
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

Appleman and Toastman like games. Today they play a game with strings with the following rules. Firstly Toastman tells Appleman two strings s and t both consisting only of letters 'A', 'B', 'C', 'D'. Then Appleman must build string s as quickly as possible. Initially he has empty string, and in one second he can append to end of the current string any contiguous substring of t.

Now, Toastman and Appleman are beginning to play the game. Toastman has already told string t to Appleman, but he hasn't come up with string s yet. Toastman only thinks, that he should choose string s consisting of n characters. Of course, he wants to find the worst string for Appleman (such string, that Appleman will spend as much time as possible during the game). Tell Toastman, how much time will Appleman spend during the game if Toastman finds the worst string for him. You can assume that Appleman plays optimally, therefore he builds any string s in minimal possible time.

Input

The first line contains an integer n (1 ≤ n ≤ 1018). The second line contains string t (1 ≤ |t| ≤ 105). String t consists of only letters 'A', 'B', 'C', 'D'. Each letter appears at least once in string t.

Output

Print a single integer — the largest possible time Appleman needs.

Examples

Input

5
ABCCAD


Output

5


Input

5
AAABACADBABBBCBDCACBCCCDDDBDCDD


Output

4

Note

In the first example, Toastman can choose s equal to "AAAAA".

In the second example, Toastman can choose s equal to "DADDA".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXL = 100500;
const int MAXV = 20 * MAXL;
int root = 1, ind = 1;
int to[MAXV][4];
char t[MAXL];
int tlen;
long long n;
int min_lost_len[4][4];
int used[4];
int len[4];
const int MAXD = 60;
long long val[MAXD][4][4];
void add(char *s, int all_len) {
  int cur_v = root;
  for (int i = 0; i < all_len && s[i]; ++i) {
    if (to[cur_v][s[i] - 'A'] == 0) {
      ++ind;
      to[cur_v][s[i] - 'A'] = ind;
    }
    cur_v = to[cur_v][s[i] - 'A'];
  }
}
int get_depth(int v, int symb) {
  if (v == 0 || to[v][symb] == 0) {
    return 0;
  }
  auto tmp_arr = {get_depth(to[v][0], symb), get_depth(to[v][1], symb),
                  get_depth(to[v][2], symb), get_depth(to[v][3], symb)};
  return *min_element(tmp_arr.begin(), tmp_arr.end()) + 1;
}
bool can_get_len(long long el_time, long long len) {
  long long res_val[4][4] = {};
  long long tmp_val[4][4];
  for (int bit = MAXD - 1; bit >= 0; --bit) {
    if (el_time & (1ll << bit)) {
      for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
          long long &res = tmp_val[i][j] = -1ll;
          for (int k = 0; k < 4; ++k) {
            long long cur_val = res_val[i][k] + val[bit][k][j];
            if (res == -1 || res > cur_val) {
              res = cur_val;
            }
          }
        }
      }
      for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
          res_val[i][j] = tmp_val[i][j];
        }
      }
    }
    long long min_val = len;
    for (int i = 0; i < 4; ++i) {
      for (int j = 0; j < 4; ++j) {
        min_val = min(min_val, res_val[i][j]);
      }
    }
    if (min_val >= len) {
      return true;
    }
  }
  return false;
}
int main() {
  scanf("%lld %s", &n, t);
  tlen = strlen(t);
  for (int i = 0; i < tlen; ++i) {
    add(t + i, 11);
  }
  for (int start_symb = 0; start_symb < 4; ++start_symb) {
    for (int end_symb = 0; end_symb < 4; ++end_symb) {
      val[0][start_symb][end_symb] =
          get_depth(to[root][start_symb], end_symb) + 1;
    }
  }
  for (int level = 1; level < MAXD; ++level) {
    for (int start_symb = 0; start_symb < 4; ++start_symb) {
      for (int end_symb = 0; end_symb < 4; ++end_symb) {
        long long &res = val[level][start_symb][end_symb];
        res = -1ll;
        for (int inter_symb = 0; inter_symb < 4; ++inter_symb) {
          long long cur_val = val[level - 1][start_symb][inter_symb] +
                              val[level - 1][inter_symb][end_symb];
          if (res == -1ll || res > cur_val) {
            res = cur_val;
          }
        }
      }
    }
  }
  long long l_bord = 0, r_bord = n + 1;
  while (l_bord < r_bord - 1) {
    long long m_bord = (l_bord + r_bord) / 2;
    if (can_get_len(m_bord, n)) {
      r_bord = m_bord;
    } else {
      l_bord = m_bord;
    }
  }
  cout << r_bord << '\n';
  return 0;
}

```