Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of `0` and `1`.

Now, Takahashi will do the operation with the following two steps |T| times.

* Insert a `0` or a `1` at any position of S of his choice.
* Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is `01101`, the digits in the odd positions are `0`, `1`, `1` from left to right, so x is incremented by 2.



Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

* 1 \leq |T| \leq 2 \times 10^5
* T consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


T


Output

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Examples

Input

1101


Output

5


Input

0111101101


Output

26
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define ALL(c) (c).begin(), (c).end()

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

int main() {
    string T;
    cin >> T;
    int n = T.size();

    V<pii> vec;
    for (auto _c : T) {
        int c = _c - '0';
        if (vec.size() == 0 || vec.back().fi != c) {
            vec.eb(c, 1);
        } else {
            vec.back().se++;
        }
    }

    debug(vec);

    ll one = 0;
    for (auto p : vec) {
        if (p.fi) {
            one += p.se;
        }
    }

    /// 111..1 -> 000..0
    ll ans = one / 2 * (one / 2 + 1) + (one % 2 ? (one + 1) / 2 : 0);
    debug(one, ans);

    ll zero = n - one;
    ll cur_zero = 0;
    ll f = 0;

    for (auto p : vec) {
        if (p.fi) {
            ans += zero * (p.se / 2);
            if (p.se & 1) {
                ans += ((cur_zero + 1 - f) / 2 + (zero - cur_zero));
            }
        } else {
            cur_zero += p.se;
        }
        f = (f + p.se) % 2;
        debug(ans);
    }

    cout << ans << endl;

    return 0;
}