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>
#pragma GCC optimize("O3")
using namespace std;
const int N = 1000031;
string st;
vector<pair<int, int> > v;
long long multiplier;
long long dp[N];
long long solve(vector<pair<int, int> > v) {
  for (int i = 0; i <= v.size(); i++) {
    dp[i] = 0;
  }
  dp[0] = 1;
  for (int i = 0; i < v.size(); i++) {
    if (v[i].first == '1') {
      for (int j = i; j >= 0; j--) {
        if (v[j].first == '1') dp[i + 1] += dp[j] * v[i].second;
        dp[i + 1] %= 1000000007;
      }
      continue;
    }
    for (int len_here = 1; len_here <= v[i].second; len_here++) {
      long long ttl = 0;
      for (int j = i - 1; j >= 0; --j) {
        if (v[j].first == '0' && v[j].second >= len_here) break;
        if (v[j].first == '1') ttl += dp[j + 1];
      }
      dp[i + 1] += ttl;
      dp[i + 1] %= 1000000007;
    }
  }
  for (int i = 0; i <= v.size(); i++) {
    cout << dp[i] << " ";
  }
  cout << endl;
  long long res = 0;
  for (int i = 0; i < v.size(); i++) {
    if (v[i].first == '1') res += dp[i + 1];
    res %= 1000000007;
  }
  return res;
}
long long dp_pref_sum[N];
int sparse[20][1 << 20];
void build_sparse(vector<pair<int, int> > v) {
  for (int i = 0; i < v.size(); i++) {
    if (v[i].first == '0')
      sparse[0][i] = v[i].second;
    else
      sparse[0][i] = 0;
  }
  for (int lev = 1; lev <= 19; ++lev) {
    for (int i = 0; i < v.size(); i++) {
      sparse[lev][i] = sparse[lev - 1][i];
      if (i - (1 << lev) / 2 >= 0)
        sparse[lev][i] =
            max(sparse[lev][i], sparse[lev - 1][i - (1 << lev) / 2]);
    }
  }
}
int get_first_block_dumb(int len_here, int i) {
  for (int j = i - 1; j >= 0; --j) {
    if (v[j].first == '0' && v[j].second >= len_here) return j;
  }
  return -1;
}
long long get_first_block(int len_here, int i) {
  --i;
  for (int lev = 19; lev >= 0; --lev) {
    if (i >= 0 && sparse[lev][i] < len_here) i -= (1 << lev);
  }
  if (i <= 0) return -1;
  return i - 1;
}
long long smart_solve(vector<pair<int, int> > v) {
  for (int i = 0; i <= v.size(); i++) {
    dp[i] = 0;
  }
  build_sparse(v);
  dp[0] = 1;
  long long sum_of_magic1 = 0;
  for (int i = 0; i < v.size(); i++) {
    if (v[i].first == '1') {
      sum_of_magic1 += dp[i];
      sum_of_magic1 %= 1000000007;
      dp[i + 1] += sum_of_magic1 * v[i].second % 1000000007;
      dp[i + 1] %= 1000000007;
      dp_pref_sum[i + 1] = dp_pref_sum[i] + dp[i + 1];
      dp_pref_sum[i + 1] %= 1000000007;
      continue;
    }
    for (int len_here = 1; len_here <= v[i].second; len_here++) {
      int PS = get_first_block(len_here, i);
      long long ttl = dp_pref_sum[i] - dp_pref_sum[PS + 1];
      if (ttl < 0) ttl += 1000000007;
      dp[i + 1] += ttl;
      dp_pref_sum[i + 1] = dp_pref_sum[i];
      dp_pref_sum[i + 1] %= 1000000007;
      dp[i + 1] %= 1000000007;
    }
  }
  long long res = 0;
  for (int i = 0; i < v.size(); i++) {
    if (v[i].first == '1') res += dp[i + 1];
    res %= 1000000007;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> st;
  int cnt = 0;
  for (int i = 0; i < st.size(); i++) {
    if (st[i] == '1') ++cnt;
  }
  if (cnt == 0) {
    cout << st.size() << endl;
    return 0;
  }
  cnt = 0;
  for (int i = 0; i < st.size(); i++) {
    if (i > 0 && st[i] != st[i - 1]) {
      v.push_back(make_pair(st[i - 1], cnt));
      cnt = 0;
    }
    cnt++;
  }
  v.push_back(make_pair(st[st.size() - 1], cnt));
  multiplier = 1;
  if (v[0].first == '0') {
    multiplier *= v[0].second + 1;
    v.erase(v.begin());
  }
  if (v[v.size() - 1].first == '0') {
    multiplier *= v[v.size() - 1].second + 1;
    multiplier %= 1000000007;
    v.erase(v.begin() + v.size() - 1);
  }
  cout << smart_solve(v) * multiplier % 1000000007 << endl;
  cin.get();
  cin.get();
  return 0;
}