#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long Inf = 1e18;
const int mod = 1e9 + 7;
template <typename T = int>
T gi() {
  T x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename T>
string to_string(T v) {
  int fst = 1;
  string ret = "{";
  for (auto x : v) {
    if (!fst) ret += ",";
    fst = 0, ret += to_string(x);
  }
  ret += "}";
  return ret;
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  dbg_out(T...);
}
template <typename T>
int qpow(int a, T b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return ret;
}
const int N = 6010;
const int base = 131;
const int mo = 998244853;
int n, g[N], h[N], f[N][N], hsh[N], pw[N];
map<string, bool> ban;
map<string, vector<int>> pos;
char s[N];
namespace SA {
int sa[N], rnk[N], ht[N], lg2[N], st[N][20];
bool cmp(int *r, int a, int b, int l) {
  return r[a] == r[b] && r[a + l] == r[b + l];
}
void build(char *s, int n, int m) {
  static int x[N], y[N], ws[N], wv[N];
  for (int i = 0; i <= m; i++) ws[i] = 0;
  for (int i = 1; i <= n; i++) ws[x[i] = s[i]]++;
  for (int i = 1; i <= m; i++) ws[i] += ws[i - 1];
  for (int i = n; i; i--) sa[ws[x[i]]--] = i;
  for (int j = 1;; j <<= 1) {
    int p = 0;
    for (int i = n - j + 1; i <= n; i++) y[++p] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (int i = 1; i <= n; i++) wv[i] = x[y[i]];
    for (int i = 0; i <= m; i++) ws[i] = 0;
    for (int i = 1; i <= n; i++) ws[wv[i]]++;
    for (int i = 1; i <= m; i++) ws[i] += ws[i - 1];
    for (int i = n; i; i--) sa[ws[wv[i]]--] = y[i];
    swap(x, y);
    x[sa[1]] = p = 1;
    for (int i = 2; i <= n; i++)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p : ++p;
    if (p == n) break;
    m = p;
  }
  for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
  for (int i = 1, j, k = 0; i <= n; ht[rnk[i++]] = k)
    for (k ? k-- : 0, j = sa[rnk[i] - 1]; s[i + k] == s[j + k]; k++)
      ;
  for (int i = 1; i <= n; i++) st[i][0] = ht[i];
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
}
int query(int l, int r) {
  int k = lg2[r - l + 1];
  return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int lcp(int i, int j) {
  i = n - i + 1, j = n - j + 1;
  if (i == j) return n - i + 1;
  if (rnk[i] > rnk[j]) swap(i, j);
  return query(rnk[i] + 1, rnk[j]);
}
}  // namespace SA
int main() {
  n = gi();
  ban["0011"] = 1;
  ban["0101"] = 1;
  ban["1110"] = 1;
  ban["1111"] = 1;
  pw[0] = 1;
  for (int i = 1; i <= n; i++) {
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    s[i] = ch;
  }
  s[n + 1] = '\0';
  reverse(s + 1, s + n + 1);
  SA::build(s, n, 1000);
  reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; i++) {
    pw[i] = 1ll * pw[i - 1] * base % mo;
    char ch = s[i];
    hsh[i] = (1ll * hsh[i - 1] * base + ch - '0' + 1) % mo;
    for (int j = 1; j <= i; j++) {
      for (int k = 1; k <= 4; k++) {
        if (k <= j) {
          string x;
          for (int l = i - k + 1; l <= i; l++) x += s[l];
          if (ban.count(x)) continue;
          inc(f[i][j], 1);
          inc(f[i][j], f[i - k][j - k]);
        }
      }
    }
    g[i] = g[i - 1];
    for (int j = 1; j <= 4; j++)
      if (i >= j) {
        string x;
        for (int k = i - j + 1; k <= i; k++) x += s[k];
        if (ban.count(x)) continue;
        if (pos[x].empty()) inc(g[i], 1);
        int maxlcp = 0, p = 0;
        for (auto y : pos[x]) {
          if (chkmax(maxlcp, SA::lcp(y - j, i - j))) p = y;
        }
        inc(g[i], f[i - j][i - j]);
        if (p) {
          dec(g[i], f[p - j][maxlcp]);
        }
        pos[x].push_back(i);
      }
    printf("%d\n", g[i]);
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

In Morse code, an letter of English alphabet is represented as a string of some length from 1 to 4. Moreover, each Morse code representation of an English letter contains only dots and dashes. In this task, we will represent a dot with a "0" and a dash with a "1".

Because there are 2^1+2^2+2^3+2^4 = 30 strings with length 1 to 4 containing only "0" and/or "1", not all of them correspond to one of the 26 English letters. In particular, each string of "0" and/or "1" of length at most 4 translates into a distinct English letter, except the following four strings that do not correspond to any English alphabet: "0011", "0101", "1110", and "1111".

You will work with a string S, which is initially empty. For m times, either a dot or a dash will be appended to S, one at a time. Your task is to find and report, after each of these modifications to string S, the number of non-empty sequences of English letters that are represented with some substring of S in Morse code.

Since the answers can be incredibly tremendous, print them modulo 10^9 + 7.

Input

The first line contains an integer m (1 ≤ m ≤ 3 000) — the number of modifications to S. 

Each of the next m lines contains either a "0" (representing a dot) or a "1" (representing a dash), specifying which character should be appended to S.

Output

Print m lines, the i-th of which being the answer after the i-th modification to S.

Examples

Input

3
1
1
1


Output

1
3
7


Input

5
1
0
1
0
1


Output

1
4
10
22
43


Input

9
1
1
0
0
0
1
1
0
1


Output

1
3
10
24
51
109
213
421
833

Note

Let us consider the first sample after all characters have been appended to S, so S is "111".

As you can see, "1", "11", and "111" all correspond to some distinct English letter. In fact, they are translated into a 'T', an 'M', and an 'O', respectively. All non-empty sequences of English letters that are represented with some substring of S in Morse code, therefore, are as follows.

  1. "T" (translates into "1") 
  2. "M" (translates into "11") 
  3. "O" (translates into "111") 
  4. "TT" (translates into "11") 
  5. "TM" (translates into "111") 
  6. "MT" (translates into "111") 
  7. "TTT" (translates into "111") 



Although unnecessary for this task, a conversion table from English alphabets into Morse code can be found [here](https://en.wikipedia.org/wiki/Morse_code).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const long long Inf = 1e18;
const int mod = 1e9 + 7;
template <typename T = int>
T gi() {
  T x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
template <typename T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
};
template <typename T>
bool chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
};
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
void inc(int &a, int b) { a = (a + b >= mod ? a + b - mod : a + b); }
void dec(int &a, int b) { a = (a - b < 0 ? a - b + mod : a - b); }
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename T>
string to_string(T v) {
  int fst = 1;
  string ret = "{";
  for (auto x : v) {
    if (!fst) ret += ",";
    fst = 0, ret += to_string(x);
  }
  ret += "}";
  return ret;
}
void dbg_out() { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  dbg_out(T...);
}
template <typename T>
int qpow(int a, T b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return ret;
}
const int N = 6010;
const int base = 131;
const int mo = 998244853;
int n, g[N], h[N], f[N][N], hsh[N], pw[N];
map<string, bool> ban;
map<string, vector<int>> pos;
char s[N];
namespace SA {
int sa[N], rnk[N], ht[N], lg2[N], st[N][20];
bool cmp(int *r, int a, int b, int l) {
  return r[a] == r[b] && r[a + l] == r[b + l];
}
void build(char *s, int n, int m) {
  static int x[N], y[N], ws[N], wv[N];
  for (int i = 0; i <= m; i++) ws[i] = 0;
  for (int i = 1; i <= n; i++) ws[x[i] = s[i]]++;
  for (int i = 1; i <= m; i++) ws[i] += ws[i - 1];
  for (int i = n; i; i--) sa[ws[x[i]]--] = i;
  for (int j = 1;; j <<= 1) {
    int p = 0;
    for (int i = n - j + 1; i <= n; i++) y[++p] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (int i = 1; i <= n; i++) wv[i] = x[y[i]];
    for (int i = 0; i <= m; i++) ws[i] = 0;
    for (int i = 1; i <= n; i++) ws[wv[i]]++;
    for (int i = 1; i <= m; i++) ws[i] += ws[i - 1];
    for (int i = n; i; i--) sa[ws[wv[i]]--] = y[i];
    swap(x, y);
    x[sa[1]] = p = 1;
    for (int i = 2; i <= n; i++)
      x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p : ++p;
    if (p == n) break;
    m = p;
  }
  for (int i = 1; i <= n; i++) rnk[sa[i]] = i;
  for (int i = 1, j, k = 0; i <= n; ht[rnk[i++]] = k)
    for (k ? k-- : 0, j = sa[rnk[i] - 1]; s[i + k] == s[j + k]; k++)
      ;
  for (int i = 1; i <= n; i++) st[i][0] = ht[i];
  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
}
int query(int l, int r) {
  int k = lg2[r - l + 1];
  return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int lcp(int i, int j) {
  i = n - i + 1, j = n - j + 1;
  if (i == j) return n - i + 1;
  if (rnk[i] > rnk[j]) swap(i, j);
  return query(rnk[i] + 1, rnk[j]);
}
}  // namespace SA
int main() {
  n = gi();
  ban["0011"] = 1;
  ban["0101"] = 1;
  ban["1110"] = 1;
  ban["1111"] = 1;
  pw[0] = 1;
  for (int i = 1; i <= n; i++) {
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    s[i] = ch;
  }
  s[n + 1] = '\0';
  reverse(s + 1, s + n + 1);
  SA::build(s, n, 1000);
  reverse(s + 1, s + n + 1);
  for (int i = 1; i <= n; i++) {
    pw[i] = 1ll * pw[i - 1] * base % mo;
    char ch = s[i];
    hsh[i] = (1ll * hsh[i - 1] * base + ch - '0' + 1) % mo;
    for (int j = 1; j <= i; j++) {
      for (int k = 1; k <= 4; k++) {
        if (k <= j) {
          string x;
          for (int l = i - k + 1; l <= i; l++) x += s[l];
          if (ban.count(x)) continue;
          inc(f[i][j], 1);
          inc(f[i][j], f[i - k][j - k]);
        }
      }
    }
    g[i] = g[i - 1];
    for (int j = 1; j <= 4; j++)
      if (i >= j) {
        string x;
        for (int k = i - j + 1; k <= i; k++) x += s[k];
        if (ban.count(x)) continue;
        if (pos[x].empty()) inc(g[i], 1);
        int maxlcp = 0, p = 0;
        for (auto y : pos[x]) {
          if (chkmax(maxlcp, SA::lcp(y - j, i - j))) p = y;
        }
        inc(g[i], f[i - j][i - j]);
        if (p) {
          dec(g[i], f[p - j][maxlcp]);
        }
        pos[x].push_back(i);
      }
    printf("%d\n", g[i]);
  }
  return 0;
}

```