#define _USE_MATH_DEFINES
 
#include <iostream>
#include <iomanip>
#include <sstream>
 
#include <algorithm>
#include <cmath>
 
#include <string>
#include <queue>
#include <vector>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <valarray>

#include<cassert>//assert();
//#include <random>//xAOJ
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
 
#define PII pair<int,int>
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
/////////
using namespace::std;
/////////
/////////

vector<ULL> to_num(string str,const int keta){
	int len = str.length();
	vector<ULL> ans = vector<ULL>(len);
	string temp;
	ULL pow10 = 1;
	for(int i= 0;i<len;++i){
		temp = str[len-i-1];
		ans[i/keta] += stoi( temp )*pow10;
		if( (i+1)%keta != 0 ){
			pow10 *= 10;
		}else{
			pow10 = 1;
		}
	}
	return ans;
}
/*
template <class T> void view( vector<T> v){
	vector<T>::iterator itr,end;
	itr = v.begin();
	end = v.end();
	for(;itr != end;++itr){
		cout << (*itr);
	}
	cout << endl;
}*/
class vnum{
public:
	vector<ULL> num;
	int len;
	int ketaMax;
	ULL powMax;
	void set(string str){
		ketaMax = 17;
		powMax = 1;

		num = to_num(str,ketaMax);
		len = numLen();
		
		for(int i=1;i<ketaMax;++i){
			powMax *= 10;
		}
	}
	int numLen(){
		int Max = num.size();
		int i;
		for(i= Max-1;i>=0;--i){
			if( num[i] != 0){
				break;
			}
		}
		return i+1;
	}
	bool mod2(){//%2
		bool ans = false;
		if( num[0] % 2 ){
			ans = true;
		}
		num[0] = num[0] / 2;
		ULL temp;
		for(int i = 1; i< len;++i){
			temp = num[i]*10;
			temp /= 2;
			num[i] = temp/10;
			num[i-1] += (temp%10)*powMax;
		}
		len = numLen();
		return ans;
	}
	void view(){
		for(int i=len-1;i>=0;--i){
			cout << num[i];
		}cout << endl;
	}
};

void solve(){
	string str;
	cin >> str;
	vnum Num;
	Num.num.reserve(100000);
	Num.set(str);
	ULL count = 0;
	ULL test = 0;
	while(Num.len != 0){
		test++;
		if( Num.mod2() ){
			++count;
		}
		//Num.view();
		if( test > 100000000)break;
	}
	cout << count%((ULL)1004535809) << endl;
}

int main(void){
    std::cin.tie(0); 
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(16);//
	
	solve();
	
	return 0;
}