#include <bits/stdc++.h>
using namespace std;
int nas[4][100015];
char napi[100015];
struct Ukkonen {
  static const int max_len = 200000;
  struct node {
    map<char, pair<node *, pair<int, int> > > trans;
    node *suflink;
    int szukaj(char D) {
      int w = max_len + 100;
      for (int i = 'A'; i <= 'D'; i++) {
        if (trans.find(i) == trans.end() && i == D) return 0;
        w = min(w, licz(i, D));
      }
      return w;
    }
    int licz(char A, char D) {
      map<char, pair<node *, pair<int, int> > >::iterator it = trans.find(A);
      if (it == trans.end()) return max_len + 10;
      pair<node *, pair<int, int> > t = (*it).second;
      if (t.second.first == t.second.second) {
        if (t.first == nullptr) return 1;
        return t.first->szukaj(D) + 1;
      }
      int z = t.second.second;
      for (int i = 'A'; i <= 'D'; i++) {
        if (i == D) continue;
        z = min(z, nas[i - 'A'][t.second.first + 1]);
      }
      if (napi[z] == D) {
        if (t.first == nullptr) return t.second.second - t.second.first;
        return t.first->szukaj(D) + t.second.second - t.second.first;
      }
      return z - t.second.first;
    }
  };
  int n;
  char nap[max_len + 5];
  node *root;
  node *pin;
  Ukkonen() : n(0), root(nullptr), pin(nullptr) {}
  void kanonizuj(node *&s, int &a, int b) {
    if (b < a) return;
    pair<node *, pair<int, int> > t = s->trans[nap[a]];
    node *sp = t.first;
    int ap = t.second.first;
    int bp = t.second.second;
    while (bp - ap <= b - a) {
      a = a + bp - ap + 1;
      s = sp;
      if (a <= b) {
        t = s->trans[nap[a]];
        sp = t.first;
        ap = t.second.first;
        bp = t.second.second;
      }
    }
  }
  bool splituj(node *s, int a, int b, char c, node *&ret) {
    if (a <= b) {
      pair<node *, pair<int, int> > &t = s->trans[nap[a]];
      node *sp = t.first;
      int ap = t.second.first;
      int bp = t.second.second;
      if (c == nap[ap + b - a + 1]) {
        ret = s;
        return true;
      }
      ret = new node();
      t.second.second = ap + b - a;
      t.first = ret;
      ret->trans[nap[ap + b - a + 1]] =
          make_pair(sp, make_pair(ap + b - a + 1, bp));
      return false;
    }
    ret = s;
    return s->trans.find(c) != s->trans.end();
  }
  void update(node *&s, int &a, int &i) {
    node *oldr = root;
    node *r;
    bool end = splituj(s, a, i - 1, nap[i], r);
    while (!end) {
      r->trans[nap[i]] = make_pair(nullptr, make_pair(i, n));
      if (oldr != root) oldr->suflink = r;
      oldr = r;
      s = s->suflink;
      kanonizuj(s, a, i - 1);
      end = splituj(s, a, i - 1, nap[i], r);
    }
    if (oldr != root) oldr->suflink = s;
  }
  void konstruuj() {
    root = new node();
    pin = new node();
    for (int i = 1; i <= n; i++)
      pin->trans[nap[i]] = make_pair(root, make_pair(i, i));
    root->suflink = pin;
    node *s = root;
    int a = 1;
    for (int i = 1; i <= n; i++) {
      update(s, a, i);
      kanonizuj(s, a, i);
    }
  }
};
const long long int infty = 2e18;
long long int dodaj(const long long int &a, const long long int &b) {
  const long long int &x = a + b;
  if (x > infty) return infty;
  return x;
}
long long int pomnoz(long long int a, long long int b) {
  long long int wyn = 0LL;
  while (b) {
    if (b % 2 == 1) wyn = dodaj(wyn, a);
    a = dodaj(a, a);
    b /= 2;
  }
  return wyn;
}
long long int tab[4][4];
long long int mnoz[10][4][4];
long long int n;
void dawaj(int a, int b, int c) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) mnoz[c][i][j] = n + 1;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 0; k < 4; k++)
        mnoz[c][i][j] = min(mnoz[c][i][j], dodaj(mnoz[a][i][k], mnoz[b][k][j]));
}
bool ok(long long int c) {
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      mnoz[0][i][j] = 0;
      mnoz[2][i][j] = tab[i][j];
    }
  }
  for (int i = 0; i < 4; i++) mnoz[0][i][i] = 1;
  int w = 0, g = 2;
  c--;
  while (c) {
    if (c % 2 == 1) {
      dawaj(w, g, w ^ 1);
      w ^= 1;
    }
    dawaj(g, g, g ^ 1);
    g ^= 1;
    c /= 2;
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (mnoz[w][i][j] < n) return true;
  return false;
}
int main() {
  Ukkonen u;
  scanf("%lld", &n);
  scanf("%s", u.nap + 1);
  u.n = strlen(u.nap + 1);
  for (int i = 1; i <= u.n; i++) napi[i] = u.nap[i];
  for (int i = 0; i < 4; i++) nas[i][u.n + 1] = u.n + 3;
  for (int i = u.n; i >= 1; i--) {
    for (int j = 0; j < 4; j++) nas[j][i] = nas[j][i + 1];
    nas[u.nap[i] - 'A'][i] = i;
  }
  u.konstruuj();
  for (int i = 'A'; i <= 'D'; i++)
    for (int j = 'A'; j <= 'D'; j++) tab[i - 'A'][j - 'A'] = u.root->licz(i, j);
  long long int a = 1LL, b = n, c;
  while (a < b) {
    c = (a + b + 1) / 2;
    if (ok(c))
      a = c;
    else
      b = c - 1;
  }
  printf("%lld\n", a);
  return 0;
}

### Prompt

Your task is to create 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;
int nas[4][100015];
char napi[100015];
struct Ukkonen {
  static const int max_len = 200000;
  struct node {
    map<char, pair<node *, pair<int, int> > > trans;
    node *suflink;
    int szukaj(char D) {
      int w = max_len + 100;
      for (int i = 'A'; i <= 'D'; i++) {
        if (trans.find(i) == trans.end() && i == D) return 0;
        w = min(w, licz(i, D));
      }
      return w;
    }
    int licz(char A, char D) {
      map<char, pair<node *, pair<int, int> > >::iterator it = trans.find(A);
      if (it == trans.end()) return max_len + 10;
      pair<node *, pair<int, int> > t = (*it).second;
      if (t.second.first == t.second.second) {
        if (t.first == nullptr) return 1;
        return t.first->szukaj(D) + 1;
      }
      int z = t.second.second;
      for (int i = 'A'; i <= 'D'; i++) {
        if (i == D) continue;
        z = min(z, nas[i - 'A'][t.second.first + 1]);
      }
      if (napi[z] == D) {
        if (t.first == nullptr) return t.second.second - t.second.first;
        return t.first->szukaj(D) + t.second.second - t.second.first;
      }
      return z - t.second.first;
    }
  };
  int n;
  char nap[max_len + 5];
  node *root;
  node *pin;
  Ukkonen() : n(0), root(nullptr), pin(nullptr) {}
  void kanonizuj(node *&s, int &a, int b) {
    if (b < a) return;
    pair<node *, pair<int, int> > t = s->trans[nap[a]];
    node *sp = t.first;
    int ap = t.second.first;
    int bp = t.second.second;
    while (bp - ap <= b - a) {
      a = a + bp - ap + 1;
      s = sp;
      if (a <= b) {
        t = s->trans[nap[a]];
        sp = t.first;
        ap = t.second.first;
        bp = t.second.second;
      }
    }
  }
  bool splituj(node *s, int a, int b, char c, node *&ret) {
    if (a <= b) {
      pair<node *, pair<int, int> > &t = s->trans[nap[a]];
      node *sp = t.first;
      int ap = t.second.first;
      int bp = t.second.second;
      if (c == nap[ap + b - a + 1]) {
        ret = s;
        return true;
      }
      ret = new node();
      t.second.second = ap + b - a;
      t.first = ret;
      ret->trans[nap[ap + b - a + 1]] =
          make_pair(sp, make_pair(ap + b - a + 1, bp));
      return false;
    }
    ret = s;
    return s->trans.find(c) != s->trans.end();
  }
  void update(node *&s, int &a, int &i) {
    node *oldr = root;
    node *r;
    bool end = splituj(s, a, i - 1, nap[i], r);
    while (!end) {
      r->trans[nap[i]] = make_pair(nullptr, make_pair(i, n));
      if (oldr != root) oldr->suflink = r;
      oldr = r;
      s = s->suflink;
      kanonizuj(s, a, i - 1);
      end = splituj(s, a, i - 1, nap[i], r);
    }
    if (oldr != root) oldr->suflink = s;
  }
  void konstruuj() {
    root = new node();
    pin = new node();
    for (int i = 1; i <= n; i++)
      pin->trans[nap[i]] = make_pair(root, make_pair(i, i));
    root->suflink = pin;
    node *s = root;
    int a = 1;
    for (int i = 1; i <= n; i++) {
      update(s, a, i);
      kanonizuj(s, a, i);
    }
  }
};
const long long int infty = 2e18;
long long int dodaj(const long long int &a, const long long int &b) {
  const long long int &x = a + b;
  if (x > infty) return infty;
  return x;
}
long long int pomnoz(long long int a, long long int b) {
  long long int wyn = 0LL;
  while (b) {
    if (b % 2 == 1) wyn = dodaj(wyn, a);
    a = dodaj(a, a);
    b /= 2;
  }
  return wyn;
}
long long int tab[4][4];
long long int mnoz[10][4][4];
long long int n;
void dawaj(int a, int b, int c) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) mnoz[c][i][j] = n + 1;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 0; k < 4; k++)
        mnoz[c][i][j] = min(mnoz[c][i][j], dodaj(mnoz[a][i][k], mnoz[b][k][j]));
}
bool ok(long long int c) {
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      mnoz[0][i][j] = 0;
      mnoz[2][i][j] = tab[i][j];
    }
  }
  for (int i = 0; i < 4; i++) mnoz[0][i][i] = 1;
  int w = 0, g = 2;
  c--;
  while (c) {
    if (c % 2 == 1) {
      dawaj(w, g, w ^ 1);
      w ^= 1;
    }
    dawaj(g, g, g ^ 1);
    g ^= 1;
    c /= 2;
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      if (mnoz[w][i][j] < n) return true;
  return false;
}
int main() {
  Ukkonen u;
  scanf("%lld", &n);
  scanf("%s", u.nap + 1);
  u.n = strlen(u.nap + 1);
  for (int i = 1; i <= u.n; i++) napi[i] = u.nap[i];
  for (int i = 0; i < 4; i++) nas[i][u.n + 1] = u.n + 3;
  for (int i = u.n; i >= 1; i--) {
    for (int j = 0; j < 4; j++) nas[j][i] = nas[j][i + 1];
    nas[u.nap[i] - 'A'][i] = i;
  }
  u.konstruuj();
  for (int i = 'A'; i <= 'D'; i++)
    for (int j = 'A'; j <= 'D'; j++) tab[i - 'A'][j - 'A'] = u.root->licz(i, j);
  long long int a = 1LL, b = n, c;
  while (a < b) {
    c = (a + b + 1) / 2;
    if (ok(c))
      a = c;
    else
      b = c - 1;
  }
  printf("%lld\n", a);
  return 0;
}

```