#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include//assert(); //#include //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)< ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// ///////// vector to_num(string str,const int keta){ int len = str.length(); vector ans = vector(len); string temp; ULL pow10 = 1; for(int i= 0;i void view( vector v){ vector::iterator itr,end; itr = v.begin(); end = v.end(); for(;itr != end;++itr){ cout << (*itr); } cout << endl; }*/ class vnum{ public: vector 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=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 > 10000)break; //if( test > 1000000)break;//TLE } 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; }