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;
template <typename T1, typename T2>
inline void chkmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chkmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int MAXN = 1000228;
const int Mod = 1000000007;
int sum(int a, int b) { return (a + b >= Mod ? a + b - Mod : a + b); }
int mul(int a, int b) { return ((ll)a * b) % Mod; }
string s;
int dp[MAXN];
int nxt[MAXN][2];
int dp1[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s;
  nxt[(int)(s).size()][0] = (int)(s).size();
  nxt[(int)(s).size()][1] = (int)(s).size();
  for (int i = (int)(s).size() - 1; i >= 0; i--) {
    nxt[i][0] = nxt[i + 1][0];
    nxt[i][1] = nxt[i + 1][1];
    nxt[i][s[i] - '0'] = i;
  }
  int last = (int)(s).size();
  int tot = 0;
  int rem = 0;
  for (int i = (int)(s).size() - 1; i >= 0; i--) {
    if (s[i] == '1') {
      if (last < (int)(s).size()) {
        for (int j = 1; j < last - i; j++) {
          tot = sum(tot, Mod - dp1[j]);
          dp1[j] = dp[last];
          tot = sum(tot, dp1[j]);
        }
      } else {
        rem = last - i;
      }
      dp[i] = dp[nxt[i + 1][1]];
      dp[i] = sum(dp[i], tot);
      dp[i] = sum(dp[i], rem);
      last = i;
    }
  }
  int uk = 0;
  while (s[uk] == '0' && uk < (int)(s).size()) {
    uk++;
  }
  if (uk == (int)(s).size()) {
    cout << uk << '\n';
    return 0;
  }
  cout << mul(dp[last], uk + 1) << '\n';
}