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;
namespace debug {
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
char elo(...);
template <class c>
auto elo(c* a) -> decltype(cerr << *a, 0);
struct stream {
  ~stream() { cerr << endl; }
  template <class c>
  typename enable_if<sizeof elo<c>(0) != 1, stream&>::type operator<<(c i) {
    cerr << boolalpha << i;
    return *this;
  }
  template <class c>
  typename enable_if<sizeof elo<c>(0) == 1, stream&>::type operator<<(c i) {
    return *this << range(begin(i), end(i));
  }
  template <class a, class b>
  stream& operator<<(pair<a, b> p) {
    return *this << "(" << p.first << ", " << p.second << ")";
  }
  template <class c>
  stream& operator<<(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; it++) *this << ", " + 2 * (it == d.b) << *it;
    return *this << "]";
  }
  stream& _dbg(const string& s, int i, int b) {}
  template <class c, class... cs>
  stream& _dbg(const string& s, int i, int b, c arg, cs... args) {
    if (i == s.size()) return (*this << ": " << arg << "");
    b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{');
    b -= (s[i] == ')') + (s[i] == ']') + (s[i] == '}');
    if (s[i] == ',' && b == 0)
      return (*this << ": " << arg << "     ")._dbg(s, i + 1, b, args...);
    return (s[i] == ' ' ? *this : *this << s[i])
        ._dbg(s, i + 1, b, arg, args...);
  }
};
}  // namespace debug
template <class p, class q>
pair<p, q> operator-(pair<p, q> a, pair<p, q> b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
template <class p, class q>
pair<p, q> operator+(pair<p, q> a, pair<p, q> b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
template <class p, class q>
void umin(p& a, const q& b) {
  if (a > b) a = b;
}
template <class p, class q>
void umax(p& a, const q& b) {
  if (a < b) a = b;
}
using lf = long double;
using ll = long long;
using cll = const ll;
using cint = const int;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const int mod = 1000000007;
const int N = 1000005;
int n, i, j;
string t;
ll dp[N];
char str[N];
vector<int> vec;
int main() {
  scanf("%s", str);
  t = str;
  int suf0 = 0;
  while (!t.empty() && t.back() == '0') {
    suf0++;
    t.pop_back();
  }
  if (t.empty()) return printf("%d\n", suf0), 0;
  n = ((int)((t).size()));
  vec = {0};
  for (i = 0; i < n; i++) {
    if (t[i] == '0') vec.back()++;
    if (t[i] == '1') {
      vec.back()++;
      vec.push_back(0);
    };
  }
  assert(vec.back() == 0);
  vec.pop_back();
  reverse(vec.begin(), vec.end());
  int a = vec.back();
  vec.pop_back();
  reverse(vec.begin(), vec.end());
  ll all = a;
  for (int a : vec) {
    ll cnt = 0;
    for (i = 1; i <= a; i++) {
      cnt += all + mod - dp[i];
      cnt %= mod;
      dp[i] += all + mod - dp[i];
      dp[i] %= mod;
    }
    all += cnt;
    all %= mod;
  }
  all *= ll(suf0 + 1);
  all %= mod;
  printf("%lld\n", all);
  return 0;
}