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("O3")
#pragma GCC target("sse4")
using namespace std;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001;
struct mi {
  long long v;
  explicit operator long long() const { return v; }
  mi() { v = 0; }
  mi(long long _v) {
    v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
    if (v < 0) v += MOD;
  }
  friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
  mi& operator+=(const mi& m) {
    if ((v += m.v) >= MOD) v -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((v -= m.v) < 0) v += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    v = v * m.v % MOD;
    return *this;
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  friend mi pow(mi a, long long p) {
    mi ans = 1;
    assert(p >= 0);
    for (; p; p /= 2, a *= a)
      if (p & 1) ans *= a;
    return ans;
  }
  friend mi inv(const mi& a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  mi operator-() const { return mi(-v); }
  mi& operator++() { return *this += 1; }
  mi& operator--() { return *this -= 1; }
  mi operator++(int) {
    mi temp;
    temp.v = v++;
    return temp;
  }
  mi operator--(int) {
    mi temp;
    temp.v = v--;
    return temp;
  }
  friend mi operator+(mi a, const mi& b) { return a += b; }
  friend mi operator-(mi a, const mi& b) { return a -= b; }
  friend mi operator*(mi a, const mi& b) { return a *= b; }
  friend mi operator/(mi a, const mi& b) { return a /= b; }
  friend ostream& operator<<(ostream& os, const mi& m) {
    os << m.v;
    return os;
  }
  friend istream& operator>>(istream& is, mi& m) {
    long long x;
    is >> x;
    m.v = x;
    return is;
  }
};
const long long identity = 0;
const long long SZ = 131072 * 8;
mi sum[2 * SZ], lazy[2 * SZ];
bool need[2 * SZ];
mi combine(mi A, mi B) { return A + B; }
mi combineUpd(mi A, mi B) { return A + B; }
void push(int index, long long L, long long R) {
  if (!need[index]) return;
  sum[index] = lazy[index] * (R - L + 1);
  if (L != R) {
    lazy[2 * index] = lazy[index];
    lazy[2 * index + 1] = lazy[index];
    need[2 * index] = true;
    need[2 * index + 1] = true;
  }
  need[index] = false;
}
void pull(int index) {
  sum[index] = combine(sum[2 * index], sum[2 * index + 1]);
}
mi query(int lo, int hi, int index = 1, long long L = 0, long long R = SZ - 1) {
  push(index, L, R);
  if (lo > R || L > hi) return identity;
  if (lo <= L && R <= hi) return sum[index];
  int M = (L + R) / 2;
  return combine(query(lo, hi, 2 * index, L, M),
                 query(lo, hi, 2 * index + 1, M + 1, R));
}
void update(int lo, int hi, mi increase, int index = 1, long long L = 0,
            long long R = SZ - 1) {
  push(index, L, R);
  if (hi < L || R < lo) return;
  if (lo <= L && R <= hi) {
    lazy[index] = increase;
    need[index] = true;
    push(index, L, R);
    return;
  }
  int M = (L + R) / 2;
  update(lo, hi, increase, 2 * index, L, M);
  update(lo, hi, increase, 2 * index + 1, M + 1, R);
  pull(index);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string S;
  cin >> S;
  int N = (int)(S).size();
  mi sumD, sumI;
  bool found = false;
  for (int i = 0; i < (N); i++)
    if (S[i] == '1') found = true;
  if (!found) {
    cout << N << nl;
    return 0;
  }
  int cur = 0;
  int lc = 0;
  int lst = 0;
  vector<pair<int, int> > A;
  for (int i = 0; i < (N); i++) {
    if (S[i] - '0' != lst) {
      if (lst == 1) {
        A.push_back({cur, lc});
      }
      lc = cur;
      cur = 0;
      lst = S[i] - '0';
    }
    cur++;
  }
  mi prod = 1;
  if (lst == 1) {
    A.push_back({cur, lc});
  } else {
    prod += cur;
  }
  sumD = A[0].second + 1;
  sumI = sumD * A[0].first;
  for (int i = 1; i < ((int)(A).size()); i++) {
    mi oi = sumI;
    sumI += sumD * A[i].first;
    mi term = oi * A[i].second - query(1, A[i].second);
    sumD += term;
    sumI += term * A[i].first;
    update(1, A[i].second, oi);
  }
  cout << sumI * prod << nl;
  return 0;
}