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;
#define rep(i, n) for(long long i=0; i<(long long)(n); i++)
#define REP(i, k, n) for(long long i=(long long)(k); i<(long long)(n); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define PQ(T) priority_queue<T>
#define PQS(T) priority_queue<T, vector<T>, greater<T> >
#define deci cout << fixed << setprecision(15);
typedef long long ll;
const ll inf = 1020304050607080910;
const ll mod = 1000000007;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
ll gcd(ll x,ll y){if(x>y)swap(x, y);while(x!=0){y%=x;swap(x, y);}return y;}
ll mpow(ll x,ll r){if(r==0)return 1;if(r%2==1){return x*mpow(x,r-1)%mod;}else{ll aa=mpow(x,r/2);return aa*aa%mod;}}

int main(){
	string T; cin >> T;
	ll cnt = 0, ans = 0, s[T.size()], sum = 0;
	vector<P> num;
	rep(i, T.size()){
		if(i==0){
			cnt++;
			s[i] = ((T[i]=='0')?1:0);
		}else if(T[i] != T[i-1]){
			if(T[i-1]=='1') num.pb(P(cnt, i-1));
			cnt = 1;
			s[i] = s[i-1] + ((T[i]=='0')?1:0);
		}else{
			cnt++;
			s[i] = s[i-1] + ((T[i]=='0')?1:0);
		}
		sum += ((T[i]=='0')?1:0);
	}
	if(T[T.size()-1]=='1') num.pb(P(cnt, T.size()-1));
	ll p = T.size() - sum;
	if(p%2==0) ans = (1+(p/2))*(p/2);
	else ans = (1+(p/2))*(p/2)+(p+1)/2;
	if(T[0] == '0'){
		ll ss = 0;
		rep(i, num.size()){
			ll q = num[i].first, r = num[i].second;
			ans += q*(s[r]/2) + (sum-s[r])*((q+1)/2);
			if(ss%2==0 && s[r]%2==1) ans += q/2;
			else if(ss%2==1 && s[r]%2==1) ans += (q+1)/2;
			ss += q;
		}
	}else{
		ll ss = num[0].first;
		ans += ((num[0].first+1)/2)*sum;
		rep(i, num.size()-1){
			ll q = num[i+1].first, r = num[i+1].second;
			ans += q*(s[r]/2) + (sum-s[r])*((q+1)/2);
			if(ss%2==0 && s[r]%2==1) ans += q/2;
			else if(ss%2==1 && s[r]%2==1) ans += (q+1)/2;
			ss += q;
		}
	}
	cout << ans << endl;
	return 0;
}
