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 A, size_t N, typename T>
void Fill(A (&array)[N], const T& val) {
  std::fill((T*)array, (T*)(array + N), val);
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <unsigned int mod>
class ModInt {
 private:
  unsigned int v;
  static unsigned int norm(const unsigned int& x) {
    return x < mod ? x : x - mod;
  }
  static ModInt make(const unsigned int& x) {
    ModInt m;
    return m.v = x, m;
  }
  static ModInt inv(const ModInt& x) { return make(inverse(x.v, mod)); }
  static unsigned int inverse(int a, int m) {
    int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t;
    while (*v) {
      t = *u / *v;
      swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]),
          swap(u[2] -= t * v[2], v[2]);
    }
    return (u[1] % m + m) % m;
  }

 public:
  ModInt() : v{0} {}
  ModInt(const long long val) : v{norm(val % mod + mod)} {}
  ModInt(const ModInt<mod>& n) : v{n()} {}
  explicit operator bool() const noexcept { return v != 0; }
  bool operator!() const noexcept { return !static_cast<bool>(*this); }
  ModInt& operator=(const ModInt& n) { return v = n(), (*this); }
  ModInt& operator=(const long long val) {
    return v = norm(val % mod + mod), (*this);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { return v == 0 ? make(0) : make(mod - v); }
  ModInt operator+(const ModInt& val) const { return make(norm(v + val())); }
  ModInt operator-(const ModInt& val) const {
    return make(norm(v + mod - val()));
  }
  ModInt operator*(const ModInt& val) const {
    return make((long long)v * val() % mod);
  }
  ModInt operator/(const ModInt& val) const { return *this * inv(val); }
  ModInt& operator+=(const ModInt& val) { return *this = *this + val; }
  ModInt& operator-=(const ModInt& val) { return *this = *this - val; }
  ModInt& operator*=(const ModInt& val) { return *this = *this * val; }
  ModInt& operator/=(const ModInt& val) { return *this = *this / val; }
  ModInt operator+(const long long val) const { return ModInt{v + val}; }
  ModInt operator-(const long long val) const { return ModInt{v - val}; }
  ModInt operator*(const long long val) const {
    return ModInt{(long long)v * (val % mod)};
  }
  ModInt operator/(const long long val) const {
    return ModInt{(long long)v * inv(val)};
  }
  ModInt& operator+=(const long long val) { return *this = *this + val; }
  ModInt& operator-=(const long long val) { return *this = *this - val; }
  ModInt& operator*=(const long long val) { return *this = *this * val; }
  ModInt& operator/=(const long long val) { return *this = *this / val; }
  bool operator==(const ModInt& val) const { return v == val.v; }
  bool operator!=(const ModInt& val) const { return !(*this == val); }
  bool operator==(const long long val) const {
    return v == norm(val % mod + mod);
  }
  bool operator!=(const long long val) const { return !(*this == val); }
  unsigned int operator()() const { return v; }
  friend ModInt operator+(const long long val, const ModInt& n) {
    return n + val;
  }
  friend ModInt operator-(const long long val, const ModInt& n) {
    return ModInt{val - n()};
  }
  friend ModInt operator*(const long long val, const ModInt& n) {
    return n * val;
  }
  friend ModInt operator/(const long long val, const ModInt& n) {
    return ModInt{val} / n;
  }
  friend bool operator==(const long long val, const ModInt& n) {
    return n == val;
  }
  friend bool operator!=(const long long val, const ModInt& n) {
    return !(val == n);
  }
  friend istream& operator>>(istream& is, ModInt& n) {
    unsigned int v;
    return is >> v, n = v, is;
  }
  friend ostream& operator<<(ostream& os, const ModInt& n) {
    return (os << n());
  }
  friend ModInt mod_pow(ModInt x, long long n) {
    ModInt ans = 1;
    while (n) {
      if (n & 1) ans *= x;
      x *= x, n >>= 1;
    }
    return ans;
  }
};
using mod = ModInt<1000000007>;
mod inv[200000], fac[200000], finv[200000];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < 200000; i++) {
    inv[i] = 1000000007 - inv[1000000007 % i] * (1000000007 / i);
    fac[i] = fac[i - 1] * i;
    finv[i] = finv[i - 1] * inv[i];
  }
}
mod comb(int a, int b) {
  if (a < b) return 0;
  return fac[a] * finv[b] * finv[a - b];
}
mod dp[1000000][2];
mod ss[1000000];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int n = s.size();
  bool f = 0;
  int c = 0;
  mod res = 1;
  vector<int> a;
  for (int i = 0; i < (int)(n); ++i) {
    if (s[i] == '0')
      c++;
    else {
      if (!f) {
        res *= c + 1;
        f = 1;
        c = 0;
      } else {
        a.push_back(c + 1);
        c = 0;
      }
    }
  }
  if (a.size() == 0) {
    cout << c << endl;
    return 0;
  }
  if (c != 0) {
    res *= c + 1;
  }
  dp[0][0] = 1;
  int m = a.size();
  for (int i = 0; i < (int)(m); ++i) {
    dp[i + 1][0] += dp[i][0] * a[i];
    dp[i + 1][0] += dp[i][1] * a[i];
    mod tmp = 0;
    for (int k = a[i]; k >= 1; k--) {
      dp[i + 1][0] -= ss[k];
      tmp += ss[k];
    }
    dp[i + 1][1] = dp[i][0] + dp[i][1];
    for (int k = 1; k <= a[i]; k++) {
      ss[k] = dp[i + 1][1];
    }
  }
  cout << res * (dp[m][0] + dp[m][1]) << endl;
  return 0;
}