Problem: Koa the Koala has a binary string s of length n. Koa can perform no more than n-1 (possibly zero) operations of the following form:

In one operation Koa selects positions i and i+1 for some i with 1 ≤ i < |s| and sets s_i to max(s_i, s_{i+1}). Then Koa deletes position i+1 from s (after the removal, the remaining parts are concatenated).

Note that after every operation the length of s decreases by 1.

How many different binary strings can Koa obtain by doing no more than n-1 (possibly zero) operations modulo 10^9+7 (1000000007)?

Input

The only line of input contains binary string s (1 ≤ |s| ≤ 10^6). For all i (1 ≤ i ≤ |s|) s_i = 0 or s_i = 1.

Output

On a single line print the answer to the problem modulo 10^9+7 (1000000007).

Examples

Input


000


Output


3


Input


0101


Output


6


Input


0001111


Output


16


Input


00101100011100


Output


477

Note

In the first sample Koa can obtain binary strings: 0, 00 and 000.

In the second sample Koa can obtain binary strings: 1, 01, 11, 011, 101 and 0101. For example:

  * to obtain 01 from 0101 Koa can operate as follows: 0101 → 0(10)1 → 011 → 0(11) → 01. 
  * to obtain 11 from 0101 Koa can operate as follows: 0101 → (01)01 → 101 → 1(01) → 11. 



Parentheses denote the two positions Koa selected in each operation.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC option("arch=native", "tune=native", "no-zero-upper")
#pragma GCC target("avx2")
#pragma GCC optimize("03")
using namespace std;
long long fs[(long long)(1e6 + 5)];
long long t[(long long)(1e6 + 5)];
template <typename T>
struct ST {
  vector<T> st, lazy;
  int sz;
  T neutroL;
  ST(int n, T neutrol) : sz(n), st(4 * n), lazy(4 * n), neutroL(neutrol) {}
  T merge(T v1, T v2) { return (v1 + v2) % (long long)(1e9 + 7); }
  void up(int p, int l, int r, T v) {
    st[p] = ((r - l + 1) * v) % (long long)(1e9 + 7);
    lazy[p] = v;
  }
  void push(int p, int l, int r) {
    if (l == r) {
      lazy[p] = neutroL;
      return;
    }
    if (lazy[p] == neutroL) return;
    T v = lazy[p];
    up((p << 1), l, (l + r) >> 1, v);
    up((p << 1) + 1, ((l + r) >> 1) + 1, r, v);
    lazy[p] = neutroL;
  }
  void build(vector<T> &arr) { build(1, 0, sz - 1, arr); }
  void build(int p, int l, int r, vector<T> &arr) {
    if (l == r) {
      st[p] = arr[l];
      lazy[p] = neutroL;
      return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid, arr);
    build((p << 1) + 1, mid + 1, r, arr);
    st[p] = merge(st[p << 1], st[(p << 1) + 1]);
    lazy[p] = neutroL;
  }
  void build(T *arr) { build(1, 0, sz - 1, arr); }
  void build(int p, int l, int r, T *arr) {
    if (l == r) {
      st[p] = arr[l];
      lazy[p] = neutroL;
      return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid, arr);
    build((p << 1) + 1, mid + 1, r, arr);
    st[p] = merge(st[p << 1], st[(p << 1) + 1]);
    lazy[p] = neutroL;
  }
  void update(int L, int R, T v) { update(1, 0, sz - 1, L, R, v); }
  void update(int p, int l, int r, int L, int R, T v) {
    push(p, l, r);
    if (L <= l && r <= R) {
      up(p, l, r, v);
      return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid) update(p << 1, l, mid, L, R, v);
    if (R > mid) update((p << 1) + 1, mid + 1, r, L, R, v);
    st[p] = merge(st[p << 1], st[(p << 1) + 1]);
  }
  T query(int L, int R) { return query(1, 0, sz - 1, L, R); }
  T query(int p, int l, int r, int L, int R) {
    push(p, l, r);
    if (L <= l && r <= R) return st[p];
    int mid = (l + r) >> 1;
    if (R <= mid) return query(p << 1, l, mid, L, R);
    if (L > mid) return query((p << 1) + 1, mid + 1, r, L, R);
    return merge(query(p << 1, l, mid, L, R),
                 query((p << 1) + 1, mid + 1, r, L, R));
  }
};
long long solve(vector<long long> &v) {
  long long sum = 0;
  long long sumdp = 0;
  long long mendp = 0;
  long long last = 1;
  long long clast = 0;
  v.push_back(1);
  int sz = v.size();
  ST<long long> st((long long)(1e6 + 5), 0);
  for (int i = 0; i < sz; i += 2) {
    sumdp = (sumdp + last) % (long long)(1e9 + 7);
    mendp = (mendp + (sum * last)) % (long long)(1e9 + 7);
    sum += v[i];
    last = (sumdp * sum - mendp + (long long)(1e9 + 7)) % (long long)(1e9 + 7);
    clast = last;
    last = (last * v[i + 1]) % (long long)(1e9 + 7);
    if (i + 2 < sz)
      last = (last - st.query(1, v[i + 1]) + (long long)(1e9 + 7)) %
             (long long)(1e9 + 7);
    st.update(1, v[i + 1], clast);
  }
  return last;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string second;
  cin >> second;
  int ty = second[0] - '0';
  int cant = 0;
  int sz = 0;
  int n = second.size();
  for (int i = 0; i < n; i++) {
    if (ty != second[i] - '0') {
      fs[cant] = sz;
      t[cant] = ty;
      sz = 0;
      cant++;
      ty = 1 - ty;
    }
    sz++;
  }
  fs[cant] = sz;
  t[cant] = ty;
  cant++;
  if (fs[0] == n) {
    cout << (n) << '\n';
    return 0;
  }
  long long mul = 1;
  int ini = 0;
  if (!t[0]) {
    ini++;
    mul = fs[0] + 1;
  }
  int fin = cant - 1;
  if (!t[fin]) {
    mul = (mul * (fs[fin] + 1)) % (long long)(1e9 + 7);
    fin--;
  }
  vector<long long> ts;
  for (int i = ini; i <= fin; i++) ts.push_back(fs[i]);
  cout << ((solve(ts) * mul) % (long long)(1e9 + 7)) << '\n';
  return 0;
}