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;
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;
struct mi {
  int val;
  explicit operator int() const { return val; }
  mi() { val = 0; }
  mi(const long long& v) {
    val = (-MOD <= v && v <= MOD) ? v : v % MOD;
    if (val < 0) val += MOD;
  }
  friend ostream& operator<<(ostream& os, const mi& a) { return os << a.val; }
  friend bool operator==(const mi& a, const mi& b) { return a.val == b.val; }
  friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }
  friend bool operator<(const mi& a, const mi& b) { return a.val < b.val; }
  mi operator-() const { return mi(-val); }
  mi& operator+=(const mi& m) {
    if ((val += m.val) >= MOD) val -= MOD;
    return *this;
  }
  mi& operator-=(const mi& m) {
    if ((val -= m.val) < 0) val += MOD;
    return *this;
  }
  mi& operator*=(const mi& m) {
    val = (long long)val * m.val % MOD;
    return *this;
  }
  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 != 0);
    return pow(a, MOD - 2);
  }
  mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  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; }
};
int n, a[MAX], nxt[MAX], block[MAX], zeros[MAX];
mi dp[MAX], fwd[MAX];
bool used[MAX];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  n = (int)s.size();
  for (int i = 0; i < n; i++) a[i] = s[i] - '0';
  int bad = 0;
  for (int i = 0; i < n; i++) bad += a[i];
  if (bad == n || bad == 0) {
    cout << n << '\n';
    return 0;
  }
  int rec = -1;
  for (int i = n - 1; i >= 0; i--) {
    nxt[i] = rec;
    if (a[i]) rec = i;
  }
  int le = n - 1;
  int ri = n - 1;
  int big = 0;
  while (ri != -1) {
    while (le != 0 && a[le - 1] == a[ri]) le--;
    if (a[ri] == 0)
      big = max(big, ri - le + 1);
    else
      for (int i = le; i <= ri; i++) block[i] = big;
    le--;
    ri = le;
  }
  for (int i = 0; i < n; i++) {
    if (a[i] == 1) {
      int cnt = 0;
      for (int j = i - 1; j >= 0; j--) {
        if (a[j] == 0)
          cnt++;
        else
          break;
      }
      zeros[i] = cnt;
    }
  }
  mi tot = 0;
  int last = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (a[i] == 0)
      last++;
    else
      break;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (a[i] == 0) continue;
    dp[i] = tot + last + 1;
    for (int j = 0; j <= zeros[i]; j++) {
      tot -= fwd[j];
      fwd[j] = dp[i];
      tot += fwd[j];
    }
  }
  int first = 0;
  int first_one;
  for (int i = 0; i < n; i++) {
    if (a[i] == 0)
      first++;
    else {
      first_one = i;
      break;
    }
  }
  mi ans = dp[first_one] * (first + 1);
  cout << ans << '\n';
  return 0;
}