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;
using ll = long long;
using Vi = vector<int>;
using Pii = pair<int, int>;
int uplg(int n) { return 32 - __builtin_clz(n); }
int uplg(ll n) { return 64 - __builtin_clzll(n); }
void run();
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(18);
  run();
  return 0;
}
constexpr int MOD = 1e9 + 7;
ll modPow(ll a, ll e, ll m) {
  ll t = 1 % m;
  while (e) {
    if (e % 2) t = t * a % m;
    e /= 2;
    a = a * a % m;
  }
  return t;
}
struct Zp {
  ll first;
  Zp() : first(0) {}
  Zp(ll a) : first(a % MOD) {
    if (first < 0) first += MOD;
  }
  Zp& operator+=(Zp r) {
    first = first + r.first - MOD * (first + r.first >= MOD);
    return *this;
  }
  Zp operator+(Zp r) const {
    Zp t = *this;
    return t += r;
  };
  Zp& operator-=(Zp r) {
    first = first - r.first + MOD * (first - r.first < 0);
    return *this;
  }
  Zp operator-(Zp r) const {
    Zp t = *this;
    return t -= r;
  };
  Zp& operator*=(Zp r) {
    first = first * r.first % MOD;
    return *this;
  }
  Zp operator*(Zp r) const {
    Zp t = *this;
    return t *= r;
  };
  Zp& operator/=(Zp r) {
    first = first * r.inv().first % MOD;
    return *this;
  }
  Zp operator/(Zp r) const {
    Zp t = *this;
    return t /= r;
  };
  Zp inv() const { return pow(MOD - 2); }
  Zp pow(ll e) const { return modPow(first, e, MOD); }
  void print() { cerr << first; }
};
void answer(Zp n) {
  cout << n.first << endl;
  exit(0);
}
void run() {
  string s;
  cin >> s;
  int ones = int(count((s).begin(), (s).end(), '1'));
  if (ones == 0 || ones == int((s).size())) {
    answer(int((s).size()));
  }
  int prefZero = 0, sufZero = 0;
  while (s[prefZero] == '0') prefZero++;
  while (s.back() == '0') {
    sufZero++;
    s.pop_back();
  }
  Zp ans = Zp(prefZero + 1) * Zp(sufZero + 1);
  s = s.substr(prefZero);
  vector<Pii> segs;
  int pos = 0;
  while (pos < int((s).size())) {
    int begin = pos;
    while (pos < int((s).size()) && s[pos] == '1') pos++;
    int mid = pos;
    while (pos < int((s).size()) && s[pos] == '0') pos++;
    segs.push_back({mid - begin, pos - mid});
  }
  vector<Zp> dp(int((segs).size()));
  dp.back() = segs.back().first;
  vector<pair<int, Zp>> que;
  for (int i = int((segs).size()) - 2; i >= 0; i--) {
    while (!que.empty() && segs[que.back().first].second <= segs[i].second) {
      que.pop_back();
    }
    if (que.empty()) {
      que.push_back({i, Zp(segs[i].second) * dp[i + 1]});
    } else {
      auto p = que.back();
      que.push_back(
          {i, Zp(segs[i].second) * (dp[i + 1] - dp[p.first + 1]) + p.second});
    }
    dp[i] = dp[i + 1] + Zp(segs[i].first) * (que.back().second + 1);
  }
  ans *= dp[0];
  answer(ans);
}