text: #include <iostream>
  #include <cstdlib>
  #include <cmath>
  #include <cstring>
  #include <string>
  #include <vector>
  #include <map>
  #include <list>
  #include <queue>
  #include <stack>
  #include <bitset>
  #include <deque>
  #include <set>
  #include <sstream>
  
  using namespace std;
  
  const double EPS = 1e-10;
  const double PI = acos(-1.0);
  
  #define dump(x) cerr << #x << " = " << (x) << endl;
  #define debug(x) cerr << #x << " = " << (x) << "(L" << __LINE__ << ")" << __FILE__ << endl;
  
  #define reep(i,a,b) for( int i = (int)(a); i < (int)(b); ++i)
  #define rep(i,n) reep(i,0,n)
  
  typedef vector<int> VI;
  typedef vector<VI> VII;
  typedef vector<string> VS;
  typedef pair<int, int> PII;
  
  inline int toInt( string s ){int v; istringstream sin(s);sin >> v;return v;}
  template<class T> inline string toString( T x ){ostringstream sout;sout<<x;return sout.str();}
  
  int main(){
      const int p = 1000000;
      int n;
      cin >> n;
  
      long long int ans = 0;
      int num = 1;
      while( n != 0 ){
          if(n&1){
              ans = (ans+num)%p;
              ans %= p;
          }
          num *= 7;
          num %= p;
          n >>= 1;
      }
  
      cout << ans << endl;
                  
  }
  
  