#include <bits/stdc++.h>
using namespace std;
long long n;
string t;
struct vertex {
  int to[4], l[4], r[4];
  int parent;
  int height;
} stree[500000];
int ssz = 1;
int suff[500000];
void init(int k) {
  memset(stree[k].to, -1, sizeof stree[k].to);
  suff[k] = -1;
  stree[k].height = 0;
  stree[k].parent = 0;
}
int new_vertex(int p) {
  init(ssz);
  stree[ssz].parent = p;
  return ssz++;
}
int split(int v, int c, int l) {
  if (l == 0) return v;
  if (l == stree[v].r[c] - stree[v].l[c]) return stree[v].to[c];
  int r = new_vertex(v), tp = t[stree[v].l[c] + l] - 'A';
  stree[r].to[tp] = stree[v].to[c];
  stree[r].r[tp] = stree[v].r[c];
  stree[r].l[tp] = stree[v].l[c] + l;
  stree[v].r[c] = stree[v].l[c] + l;
  stree[v].to[c] = r;
  stree[stree[r].to[tp]].parent = r;
  stree[r].height = stree[v].height + l;
  return r;
}
int add_leaf(int v, int c, int l) {
  int r = new_vertex(v);
  stree[v].to[c] = r;
  stree[v].l[c] = l;
  stree[v].r[c] = t.size();
  stree[r].height = t.size() - l - 1 + stree[v].height;
  return r;
}
bool try_c(int vpos, int epos, int cpos, int c) {
  if (epos == 0) {
    return stree[vpos].to[c] != -1;
  } else
    return t[stree[vpos].l[cpos] + epos] == c + 'A';
}
void jump(int& vpos, int& epos, int& cpos, int l, int r) {
  epos = r - l - stree[vpos].height;
  while (stree[vpos].to[cpos] != -1 &&
         epos >= stree[vpos].r[cpos] - stree[vpos].l[cpos]) {
    int len = stree[vpos].r[cpos] - stree[vpos].l[cpos];
    vpos = stree[vpos].to[cpos];
    epos -= len;
    cpos = t[stree[vpos].height + l] - 'A';
  }
}
typedef long long mtr[4][4];
int nst[500000][4];
int pr[4][4];
long long minn(mtr a) {
  long long ans = 1LL << 62;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) ans = min(ans, a[i][j]);
  return ans;
}
void multiply(mtr a, mtr b, mtr c) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
      c[i][j] = 1LL << 62;
      for (int k = 0; k < 4; k++) {
        c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
      }
    }
}
void eq(mtr a) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) a[i][j] = (i == j);
}
void cp(mtr a, mtr b) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) b[i][j] = a[i][j];
}
void pow(mtr ao, long long p, mtr r) {
  eq(r);
  mtr buf, a;
  cp(ao, a);
  while (p > 0) {
    if (p % 2 == 1) {
      p--;
      cp(r, buf);
      multiply(a, buf, r);
    } else {
      multiply(a, a, buf);
      cp(buf, a);
      p /= 2;
    }
  }
}
long long ord[4][4];
void relax(long long& v, long long c) {
  if (v == -1)
    v = c;
  else
    v = min(v, c);
}
void mindist(int v, long long res[4]);
void mindist(int v, int c, long long res[4]) {
  for (int i = 0; i < 4; i++) {
    int ns = nst[stree[v].l[c] + 1][i];
    if (ns != -1 && ns < stree[v].r[c]) {
      relax(res[i], ns - stree[v].l[c] + stree[v].height);
    }
  }
  mindist(stree[v].to[c], res);
}
void mindist(int v, long long res[4]) {
  for (int i = 0; i < 4; i++) {
    if (stree[v].to[i] == -1) {
      relax(res[i], stree[v].height);
    } else {
      mindist(v, i, res);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  cin >> t;
  int l = 0, r = 0;
  init(0);
  suff[0] = 0;
  int vpos = 0;
  int cpos = 0;
  int epos = 0;
  int alone = -1;
  while (l < t.size() && r < t.size()) {
    int c = t[r] - 'A';
    while (l <= r && !try_c(vpos, epos, cpos, c)) {
      int b = split(vpos, cpos, epos);
      if (alone != -1) {
        suff[alone] = b;
        alone = -1;
      }
      if (suff[b] == -1) alone = b;
      add_leaf(b, c, r);
      l++;
      vpos = suff[vpos];
      cpos = t[l + stree[vpos].height] - 'A';
      if (l <= r) jump(vpos, epos, cpos, l, r);
    }
    if (alone != -1) {
      suff[alone] = vpos;
      alone = -1;
    }
    r++;
    if (l != r) jump(vpos, epos, cpos, l, r);
  }
  for (int i = 0; i < 4; i++) nst[t.size()][i] = -1;
  for (int i = t.size() - 1; i >= 0; i--)
    for (int j = 0; j < 4; j++) {
      if (j + 'A' == t[i])
        nst[i][j] = nst[i + 1][j];
      else
        nst[i][j] = i;
    }
  {
    memset(ord, -1, sizeof ord);
    for (int i = 0; i < 4; i++)
      if (stree[0].to[i] != -1) mindist(0, i, ord[i]);
  }
  {
    long long l = 0, r = n;
    mtr res;
    while (l + 1 < r) {
      long long m = (l + r) / 2;
      pow(ord, m, res);
      if (minn(res) <= n - 1)
        l = m;
      else
        r = m;
    }
    cout << l + 1;
  }
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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;
long long n;
string t;
struct vertex {
  int to[4], l[4], r[4];
  int parent;
  int height;
} stree[500000];
int ssz = 1;
int suff[500000];
void init(int k) {
  memset(stree[k].to, -1, sizeof stree[k].to);
  suff[k] = -1;
  stree[k].height = 0;
  stree[k].parent = 0;
}
int new_vertex(int p) {
  init(ssz);
  stree[ssz].parent = p;
  return ssz++;
}
int split(int v, int c, int l) {
  if (l == 0) return v;
  if (l == stree[v].r[c] - stree[v].l[c]) return stree[v].to[c];
  int r = new_vertex(v), tp = t[stree[v].l[c] + l] - 'A';
  stree[r].to[tp] = stree[v].to[c];
  stree[r].r[tp] = stree[v].r[c];
  stree[r].l[tp] = stree[v].l[c] + l;
  stree[v].r[c] = stree[v].l[c] + l;
  stree[v].to[c] = r;
  stree[stree[r].to[tp]].parent = r;
  stree[r].height = stree[v].height + l;
  return r;
}
int add_leaf(int v, int c, int l) {
  int r = new_vertex(v);
  stree[v].to[c] = r;
  stree[v].l[c] = l;
  stree[v].r[c] = t.size();
  stree[r].height = t.size() - l - 1 + stree[v].height;
  return r;
}
bool try_c(int vpos, int epos, int cpos, int c) {
  if (epos == 0) {
    return stree[vpos].to[c] != -1;
  } else
    return t[stree[vpos].l[cpos] + epos] == c + 'A';
}
void jump(int& vpos, int& epos, int& cpos, int l, int r) {
  epos = r - l - stree[vpos].height;
  while (stree[vpos].to[cpos] != -1 &&
         epos >= stree[vpos].r[cpos] - stree[vpos].l[cpos]) {
    int len = stree[vpos].r[cpos] - stree[vpos].l[cpos];
    vpos = stree[vpos].to[cpos];
    epos -= len;
    cpos = t[stree[vpos].height + l] - 'A';
  }
}
typedef long long mtr[4][4];
int nst[500000][4];
int pr[4][4];
long long minn(mtr a) {
  long long ans = 1LL << 62;
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) ans = min(ans, a[i][j]);
  return ans;
}
void multiply(mtr a, mtr b, mtr c) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) {
      c[i][j] = 1LL << 62;
      for (int k = 0; k < 4; k++) {
        c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
      }
    }
}
void eq(mtr a) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) a[i][j] = (i == j);
}
void cp(mtr a, mtr b) {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++) b[i][j] = a[i][j];
}
void pow(mtr ao, long long p, mtr r) {
  eq(r);
  mtr buf, a;
  cp(ao, a);
  while (p > 0) {
    if (p % 2 == 1) {
      p--;
      cp(r, buf);
      multiply(a, buf, r);
    } else {
      multiply(a, a, buf);
      cp(buf, a);
      p /= 2;
    }
  }
}
long long ord[4][4];
void relax(long long& v, long long c) {
  if (v == -1)
    v = c;
  else
    v = min(v, c);
}
void mindist(int v, long long res[4]);
void mindist(int v, int c, long long res[4]) {
  for (int i = 0; i < 4; i++) {
    int ns = nst[stree[v].l[c] + 1][i];
    if (ns != -1 && ns < stree[v].r[c]) {
      relax(res[i], ns - stree[v].l[c] + stree[v].height);
    }
  }
  mindist(stree[v].to[c], res);
}
void mindist(int v, long long res[4]) {
  for (int i = 0; i < 4; i++) {
    if (stree[v].to[i] == -1) {
      relax(res[i], stree[v].height);
    } else {
      mindist(v, i, res);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n;
  cin >> t;
  int l = 0, r = 0;
  init(0);
  suff[0] = 0;
  int vpos = 0;
  int cpos = 0;
  int epos = 0;
  int alone = -1;
  while (l < t.size() && r < t.size()) {
    int c = t[r] - 'A';
    while (l <= r && !try_c(vpos, epos, cpos, c)) {
      int b = split(vpos, cpos, epos);
      if (alone != -1) {
        suff[alone] = b;
        alone = -1;
      }
      if (suff[b] == -1) alone = b;
      add_leaf(b, c, r);
      l++;
      vpos = suff[vpos];
      cpos = t[l + stree[vpos].height] - 'A';
      if (l <= r) jump(vpos, epos, cpos, l, r);
    }
    if (alone != -1) {
      suff[alone] = vpos;
      alone = -1;
    }
    r++;
    if (l != r) jump(vpos, epos, cpos, l, r);
  }
  for (int i = 0; i < 4; i++) nst[t.size()][i] = -1;
  for (int i = t.size() - 1; i >= 0; i--)
    for (int j = 0; j < 4; j++) {
      if (j + 'A' == t[i])
        nst[i][j] = nst[i + 1][j];
      else
        nst[i][j] = i;
    }
  {
    memset(ord, -1, sizeof ord);
    for (int i = 0; i < 4; i++)
      if (stree[0].to[i] != -1) mindist(0, i, ord[i]);
  }
  {
    long long l = 0, r = n;
    mtr res;
    while (l + 1 < r) {
      long long m = (l + r) / 2;
      pow(ord, m, res);
      if (minn(res) <= n - 1)
        l = m;
      else
        r = m;
    }
    cout << l + 1;
  }
}

```