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>
using namespace std;
template <int MOD>
class ModInt {
 public:
  int v;
  ModInt() : v(0) {}
  ModInt(long long _v) {
    v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
    if (v < 0) v += MOD;
  }
  friend bool operator==(const ModInt &a, const ModInt &b) {
    return a.v == b.v;
  }
  friend bool operator!=(const ModInt &a, const ModInt &b) {
    return a.v != b.v;
  }
  friend bool operator<(const ModInt &a, const ModInt &b) { return a.v < b.v; }
  friend bool operator<=(const ModInt &a, const ModInt &b) {
    return a.v <= b.v;
  }
  friend bool operator>(const ModInt &a, const ModInt &b) { return a.v > b.v; }
  friend bool operator>=(const ModInt &a, const ModInt &b) {
    return a.v >= b.v;
  }
  ModInt &operator+=(const ModInt &a) {
    if ((v += a.v) >= MOD) v -= MOD;
    return *this;
  }
  ModInt &operator-=(const ModInt &a) {
    if ((v -= a.v) < 0) v += MOD;
    return *this;
  }
  ModInt &operator*=(const ModInt &a) {
    v = 1ll * v * a.v % MOD;
    return *this;
  }
  ModInt &operator/=(const ModInt &a) { return (*this) *= inverse(a); }
  friend ModInt pow(ModInt a, long long x) {
    ModInt res = 1;
    assert(x >= 0);
    for (; x; x /= 2, a *= a)
      if (x & 1) res *= a;
    return res;
  }
  friend ModInt inverse(ModInt a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
  }
  ModInt operator+() const { return ModInt(v); }
  ModInt operator-() const { return ModInt(-v); }
  ModInt operator++() const { return *this += 1; }
  ModInt operator--() const { return *this -= 1; }
  friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
  friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
  friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
  friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
  friend istream &operator>>(istream &is, ModInt &v) {
    is >> v.v;
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt &v) {
    os << v.v;
    return os;
  }
};
const int MOD = 1e9 + 7;
using Mint = ModInt<MOD>;
void Main() {
  string S;
  cin >> S;
  int N = S.size();
  int st = 0, et = N;
  while (st < et && S[st] == '0') st++;
  while (st < et && S[et - 1] == '0') et--;
  if (st == et) {
    cout << N << '\n';
    return;
  }
  vector<int> zero;
  for (int i = st + 1, last = 0; i < et; i++) {
    if (S[i] == '0') {
      last++;
    } else {
      zero.push_back(last);
      last = 0;
    }
  }
  int M = zero.size();
  vector<Mint> dp(M + 1, 1);
  Mint sum_in_stack = 0;
  vector<int> stk;
  const auto Calc = [&](int jid) -> Mint {
    if (jid == -1) return 0;
    int j = stk[jid];
    int low = (jid + 1 == stk.size()) ? -1 : zero[stk[jid + 1]];
    return (zero[j] - low) * dp[j + 1];
  };
  for (int i = M - 1; i >= 0; i--) {
    while (!stk.empty() && zero[stk.back()] <= zero[i]) {
      sum_in_stack -= Calc(int(stk.size()) - 2);
      sum_in_stack -= Calc(int(stk.size()) - 1);
      stk.pop_back();
      sum_in_stack += Calc(int(stk.size()) - 1);
    }
    sum_in_stack -= Calc(int(stk.size()) - 1);
    stk.emplace_back(i);
    sum_in_stack += Calc(int(stk.size()) - 2);
    sum_in_stack += Calc(int(stk.size()) - 1);
    dp[i] += sum_in_stack;
  }
  cout << dp[0] * (st + 1) * (N - et + 1) << '\n';
  return;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int T = 1;
  while (T--) {
    Main();
  }
  return 0;
}