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;
struct RangeMaxQuery {
  long long dat[(1 << 21) - 1];
  int size;
  void init(int n_) {
    size = 1;
    while (size < n_) size *= 2;
    for (int i = 0; i < 2 * size - 1; i++) dat[i] = 0;
  }
  void update(int k, long long a) {
    k += size - 1;
    dat[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  long long subquery(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return 0;
    if (a <= l && r <= b)
      return dat[k];
    else {
      return max(subquery(a, b, k * 2 + 1, l, (l + r) / 2),
                 subquery(a, b, k * 2 + 2, (l + r) / 2, r));
    }
  }
  long long query(int a, int b) { return subquery(a, b, 0, 0, size); }
};
const long long M = 1000010;
RangeMaxQuery seg;
int main() {
  seg.init(M);
  string S;
  int N;
  long long pr = 1;
  {
    cin >> S;
    N = S.size();
    int l = -1, r = -1;
    for (long long i = (long long)(0); i < (long long)(N); i++) {
      if (S[i] == '1' && l == -1) {
        l = i;
      }
      if (S[N - 1 - i] == '1' && r == -1) {
        r = N - 1 - i;
      }
    }
    if (l == -1) {
      cout << N << endl;
      return 0;
    }
    pr *= (l + 1);
    pr *= (N - r);
    pr %= 1000000007;
    S = S.substr(l, r - l + 1);
    N = S.size();
  }
  vector<long long> A;
  long long crt = 1, cnt = 0;
  for (long long i = (long long)(0); i < (long long)(N); i++) {
    if (S[i] - '0' != crt) {
      A.push_back(cnt);
      cnt = 0;
      crt = S[i] - '0';
    }
    cnt++;
  }
  A.push_back(cnt);
  N = A.size();
  vector<long long> dp(N + 1, 0), sum(N + 1, 0);
  long long anssum = 0;
  dp[0] = 1;
  sum[1] = dp[0] * A[0] % 1000000007;
  (anssum += dp[0] * A[0] % 1000000007) %= 1000000007;
  for (long long i = (long long)(1); i < (long long)(N); i++) {
    if (i % 2 == 0) {
      (dp[i] += dp[i - 2]) %= 1000000007;
      for (long long k = (long long)(1); k < (long long)(A[i - 1] + 1); k++) {
        long long rr = seg.query(k, M);
        (dp[i] += (sum[i] - sum[rr] + 1000000007)) %= 1000000007;
      }
      seg.update(A[i - 1], i - 1);
      (anssum += dp[i] * A[i] % 1000000007) %= 1000000007;
    }
    sum[i + 1] = (sum[i] + dp[i] * A[i] % 1000000007) % 1000000007;
  }
  cout << anssum * pr % 1000000007 << endl;
  return 0;
}