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;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string S;
  cin >> S;
  long long lo = (int)(S).size() + 1, hi = -1;
  for (int i = 0; i < ((int)(S).size()); i++) {
    if (S[i] == '1') {
      ckmin(lo, (long long)i);
      ckmax(hi, (long long)i);
    }
  }
  mi mul = (lo + 1) * ((int)(S).size() - hi);
  if (hi == -1) {
    cout << (int)(S).size() << nl;
    return 0;
  }
  string S2;
  for (int i = lo; i < (hi + 1); i++) S2 += S[i];
  S = S2;
  int N = (int)(S).size();
  mi dp[N + 1];
  for (int i = 0; i < (N + 1); i++) dp[i] = 0;
  dp[0] = 1;
  vector<vector<int> > q(N + 1);
  int cur = 0;
  for (int i = 0; i < (N); i++) {
    if (S[i] == '1') {
      cur = 0;
    } else {
      cur++;
    }
    q[cur].push_back(i);
  }
  int p[N + 1];
  for (int i = 0; i < (N + 1); i++) p[i] = 0;
  cur = 0;
  mi ans = 0;
  for (int i = 0; i < (N); i++) {
    if (S[i] == '1') {
      cur = 0;
    } else {
      cur++;
    }
    p[cur]++;
    if (p[0] < (int)(q[0]).size()) dp[q[0][p[0]]] += dp[i];
    if (cur < N && (int)(q[cur + 1]).size() > p[cur + 1])
      dp[q[cur + 1][p[cur + 1]]] += dp[i];
    if (S[i] == '1') ans += dp[i];
  }
  ans *= mul;
  cout << ans << nl;
  return 0;
}