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>
struct MI {
 private:
  char bb[1 << 14];
  FILE* f;
  char *bs, *be;
  char e;
  bool o, l;

 public:
  MI() : f(stdin), bs(0), be(0) {}
  inline char get() {
    if (o) {
      o = 0;
      return e;
    }
    if (bs == be) be = (bs = bb) + fread(bb, 1, sizeof(bb), f);
    if (bs == be) {
      l = 1;
      return -1;
    };
    return *bs++;
  }
  inline void unget(char c) {
    o = 1;
    e = c;
  }
  template <class T>
  inline MI& operator>(T&);
};
template <class T>
struct Q {
  const static bool U = T(-1) >= T(0);
};
template <>
struct Q<char> {};
template <class T>
std::ostream& operator<(std::ostream& out, const T& t) {
  return out << t;
}
using std::cout;
MI cin;
const int $n = 1000005;
const int mod = 1000000007;
inline void Add(int& x, int y) {
  if ((x += y) >= mod) x -= mod;
}
inline int sub(int x, int y) { return (x -= y) < 0 ? x + mod : x; }
int n, v[$n], f[$n], g[$n];
int main() {
  int lst = 0, pos = 0;
  char c = cin.get();
  while (c != -1 && !isspace(c)) {
    ++pos;
    if (c == '1') {
      v[n++] = pos - lst - 1;
      lst = pos;
    }
    c = cin.get();
  }
  v[n] = pos - lst;
  if (!n) return cout < pos < ('\n'), 0;
  int pre = f[0] = v[0] + 1;
  for (int i = 1; i < n; ++i) {
    long long t = 0;
    for (int c = 0; c <= v[i]; ++c) t += g[c];
    f[i] = ((long long)pre * (v[i] + 1) + t) % mod;
    std::fill(g, g + v[i] + 1, sub(0, pre));
    Add(pre, f[i]);
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i) ans += f[i];
  cout < (ans % mod * (v[n] + 1) % mod) < ('\n');
}