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;
int s;
bool bs[1000005];
int level[1000005], zeros[1000005];
int near[1000005];
long long dp[1000005];
long long seg[2097160];
long long query(int l, int r, int i, int ql, int qr) {
  if (r < ql || qr < l)
    return 0;
  else if (ql <= l && r <= qr)
    return seg[i];
  int m = (l + r) >> 1;
  return query(l, m, i << 1, ql, qr) + query(m + 1, r, i << 1 | 1, ql, qr);
}
long long query(int l, int r) { return query(1, s + 1, 1, l + 1, r + 1); }
void update(int l, int r, int i, int qk, int qv) {
  if (l == r) {
    seg[i] = qv;
    return;
  }
  int m = (l + r) >> 1;
  if (qk <= m)
    update(l, m, i << 1, qk, qv);
  else
    update(m + 1, r, i << 1 | 1, qk, qv);
  seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
void update(int k, int v) { update(1, s + 1, 1, k + 1, v); }
int main() {
  string S;
  cin >> S;
  s = S.length();
  for (int i = (1); i <= (s); i++) {
    bs[i] = (S[i - 1] == '1');
  }
  int t = s + 1;
  for (int i = (s); i >= (1); i--) {
    if (bs[i]) t = i;
    near[i] = t;
  }
  int c = 0;
  level[1] = 0;
  for (int i = (1); i <= (s); i++) {
    if (bs[i])
      c = 1;
    else if (c >= 1)
      ++c;
    level[i + 1] = c;
  }
  c = 1;
  for (int i = (s); i >= (1); i--) {
    if (!bs[i])
      ++c;
    else
      zeros[i] = c, c = 1;
  }
  for (int i = (1); i <= (s + 1); i++) seg[i] = 0;
  dp[s] = 1;
  dp[s + 1] = 0;
  vector<pair<int, int> > updates;
  int lastOne = bs[s] ? s : 0;
  if (lastOne) updates.push_back({level[s], dp[s]});
  for (int i = (s - 1); i >= (1); i--) {
    if (bs[i]) {
      long long p = 0;
      for (auto u : updates) {
        update(u.first, u.second - p);
        p = u.second;
      }
      updates.clear();
    }
    if (bs[i]) {
      dp[i] = (dp[i + 1] + query(zeros[i] + 1, s) + 1) % 1000000007;
    } else {
      dp[i] = dp[i + 1];
      if (near[i] > s) {
        dp[i] = (dp[i] + 1) % 1000000007;
      } else {
        dp[i] = (dp[i] + 1) % 1000000007;
        if (near[i] < s) {
          dp[i] = (dp[i] + query(1, s)) % 1000000007;
        }
      }
    }
    if (lastOne) {
      dp[i] = (dp[i] + dp[lastOne + 1]) % 1000000007;
    }
    if (!lastOne && bs[i]) lastOne = i;
    if (lastOne) updates.push_back({level[i], dp[i]});
  }
  printf("%lld\n", dp[1]);
  return 0;
}