public static void main ( String [ ] args ) {
  Scanner scan = new Scanner ( System . in ) ;
  long n = scan . nextLong ( ) ;
  int B = 62 ;
  long [ ] [ ] dp = new long [ 3 ] [ B ] ;
  dp [ 0 ] [ B - 1 ] = 1 ;
  for ( int i = B - 2 ;
  i >= 0 ;
  -- i ) {
    for ( int a = 0 ;
    a <= 2 ;
    ++ a ) {
      if ( n >>> i < a ) continue ;
      long m = n >>> i ;
      int b = ( int ) ( m / 2 - ( m - a ) / 2 ) ;
      int c = ( int ) ( ( m - a ) % 2 ) ;
      if ( c != 0 ) dp [ a ] [ i ] = dp [ b ] [ i + 1 ] % MOD ;
      else dp [ a ] [ i ] = ( dp [ b ] [ i + 1 ] + dp [ b + 1 ] [ i + 1 ] ) % MOD ;
    }
  }
  long [ ] r = new long [ B ] , s = new long [ B ] ;
  r [ 0 ] = 1 ;
  s [ 0 ] = 0 ;
  for ( int i = 1 ;
  i < B ;
  ++ i ) r [ i ] = ( 3 * r [ i - 1 ] + MOD - 1 ) % MOD ;
  for ( int i = 1 ;
  i < B ;
  ++ i ) s [ i ] = ( 3 * s [ i - 1 ] + 1 ) % MOD ;
  long t = 0 ;
  for ( int i = B - 2 ;
  i >= 0 ;
  -- i ) {
    if ( ( n & 1L << i ) != 0 ) {
      t += dp [ 1 ] [ i ] * r [ i ] % MOD ;
      t += dp [ 2 ] [ i ] * s [ i ] % MOD ;
      t %= MOD ;
    }
  }
  t = ( t + dp [ 0 ] [ 0 ] ) % MOD ;
  System . out . println ( t ) ;
}

public static void main ( String [ ] args ) { Scanner scan = new Scanner ( System . in ) ; long n = scan . nextLong ( ) ; int B = 62 ; long [ ] [ ] dp = new long [ 3 ] [ B ] ; dp [ 0 ] [ B - 1 ] = 1 ; for ( int i = B - 2 ; i >= 0 ; -- i ) { for ( int a = 0 ; a <= 2 ; ++ a ) { if ( n >>> i < a ) continue ; long m = n >>> i ; int b = ( int ) ( m / 2 - ( m - a ) / 2 ) ; int c = ( int ) ( ( m - a ) % 2 ) ; if ( c != 0 ) dp [ a ] [ i ] = dp [ b ] [ i + 1 ] % MOD ; else dp [ a ] [ i ] = ( dp [ b ] [ i + 1 ] + dp [ b + 1 ] [ i + 1 ] ) % MOD ; } } long [ ] r = new long [ B ] , s = new long [ B ] ; r [ 0 ] = 1 ; s [ 0 ] = 0 ; for ( int i = 1 ; i < B ; ++ i ) r [ i ] = ( 3 * r [ i - 1 ] + MOD - 1 ) % MOD ; for ( int i = 1 ; i < B ; ++ i ) s [ i ] = ( 3 * s [ i - 1 ] + 1 ) % MOD ; long t = 0 ; for ( int i = B - 2 ; i >= 0 ; -- i ) { if ( ( n & 1L << i ) != 0 ) { t += dp [ 1 ] [ i ] * r [ i ] % MOD ; t += dp [ 2 ] [ i ] * s [ i ] % MOD ; t %= MOD ; } } t = ( t + dp [ 0 ] [ 0 ] ) % MOD ; System . out . println ( t ) ; }
(method_declaration (modifiers) type: (void_type) name: (identifier) parameters: (formal_parameters (formal_parameter type: (array_type element: (type_identifier) dimensions: (dimensions)) name: (identifier))) body: (block (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (object_creation_expression type: (type_identifier) arguments: (argument_list (field_access object: (identifier) field: (identifier)))))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (method_invocation object: (identifier) name: (identifier) arguments: (argument_list)))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) (local_variable_declaration type: (array_type element: (integral_type) dimensions: (dimensions)) declarator: (variable_declarator name: (identifier) value: (array_creation_expression type: (integral_type) dimensions: (dimensions_expr (decimal_integer_literal)) dimensions: (dimensions_expr (identifier))))) (expression_statement (assignment_expression left: (array_access array: (array_access array: (identifier) index: (decimal_integer_literal)) index: (binary_expression left: (identifier) right: (decimal_integer_literal))) right: (decimal_integer_literal))) (for_statement init: (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (binary_expression left: (identifier) right: (decimal_integer_literal)))) condition: (binary_expression left: (identifier) right: (decimal_integer_literal)) update: (update_expression (identifier)) body: (block (for_statement init: (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) condition: (binary_expression left: (identifier) right: (decimal_integer_literal)) update: (update_expression (identifier)) body: (block (if_statement condition: (parenthesized_expression (binary_expression left: (binary_expression left: (identifier) right: (identifier)) right: (identifier))) consequence: (continue_statement)) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (binary_expression left: (identifier) right: (identifier)))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (cast_expression type: (integral_type) value: (parenthesized_expression (binary_expression left: (binary_expression left: (identifier) right: (decimal_integer_literal)) right: (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (identifier))) right: (decimal_integer_literal))))))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (cast_expression type: (integral_type) value: (parenthesized_expression (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (identifier))) right: (decimal_integer_literal)))))) (if_statement condition: (parenthesized_expression (binary_expression left: (identifier) right: (decimal_integer_literal))) consequence: (expression_statement (assignment_expression left: (array_access array: (array_access array: (identifier) index: (identifier)) index: (identifier)) right: (binary_expression left: (array_access array: (array_access array: (identifier) index: (identifier)) index: (binary_expression left: (identifier) right: (decimal_integer_literal))) right: (identifier)))) alternative: (expression_statement (assignment_expression left: (array_access array: (array_access array: (identifier) index: (identifier)) index: (identifier)) right: (binary_expression left: (parenthesized_expression (binary_expression left: (array_access array: (array_access array: (identifier) index: (identifier)) index: (binary_expression left: (identifier) right: (decimal_integer_literal))) right: (array_access array: (array_access array: (identifier) index: (binary_expression left: (identifier) right: (decimal_integer_literal))) index: (binary_expression left: (identifier) right: (decimal_integer_literal))))) right: (identifier))))))))) (local_variable_declaration type: (array_type element: (integral_type) dimensions: (dimensions)) declarator: (variable_declarator name: (identifier) value: (array_creation_expression type: (integral_type) dimensions: (dimensions_expr (identifier)))) declarator: (variable_declarator name: (identifier) value: (array_creation_expression type: (integral_type) dimensions: (dimensions_expr (identifier))))) (expression_statement (assignment_expression left: (array_access array: (identifier) index: (decimal_integer_literal)) right: (decimal_integer_literal))) (expression_statement (assignment_expression left: (array_access array: (identifier) index: (decimal_integer_literal)) right: (decimal_integer_literal))) (for_statement init: (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) condition: (binary_expression left: (identifier) right: (identifier)) update: (update_expression (identifier)) body: (expression_statement (assignment_expression left: (array_access array: (identifier) index: (identifier)) right: (binary_expression left: (parenthesized_expression (binary_expression left: (binary_expression left: (binary_expression left: (decimal_integer_literal) right: (array_access array: (identifier) index: (binary_expression left: (identifier) right: (decimal_integer_literal)))) right: (identifier)) right: (decimal_integer_literal))) right: (identifier))))) (for_statement init: (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) condition: (binary_expression left: (identifier) right: (identifier)) update: (update_expression (identifier)) body: (expression_statement (assignment_expression left: (array_access array: (identifier) index: (identifier)) right: (binary_expression left: (parenthesized_expression (binary_expression left: (binary_expression left: (decimal_integer_literal) right: (array_access array: (identifier) index: (binary_expression left: (identifier) right: (decimal_integer_literal)))) right: (decimal_integer_literal))) right: (identifier))))) (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (decimal_integer_literal))) (for_statement init: (local_variable_declaration type: (integral_type) declarator: (variable_declarator name: (identifier) value: (binary_expression left: (identifier) right: (decimal_integer_literal)))) condition: (binary_expression left: (identifier) right: (decimal_integer_literal)) update: (update_expression (identifier)) body: (block (if_statement condition: (parenthesized_expression (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (binary_expression left: (decimal_integer_literal) right: (identifier)))) right: (decimal_integer_literal))) consequence: (block (expression_statement (assignment_expression left: (identifier) right: (binary_expression left: (binary_expression left: (array_access array: (array_access array: (identifier) index: (decimal_integer_literal)) index: (identifier)) right: (array_access array: (identifier) index: (identifier))) right: (identifier)))) (expression_statement (assignment_expression left: (identifier) right: (binary_expression left: (binary_expression left: (array_access array: (array_access array: (identifier) index: (decimal_integer_literal)) index: (identifier)) right: (array_access array: (identifier) index: (identifier))) right: (identifier)))) (expression_statement (assignment_expression left: (identifier) right: (identifier))))))) (expression_statement (assignment_expression left: (identifier) right: (binary_expression left: (parenthesized_expression (binary_expression left: (identifier) right: (array_access array: (array_access array: (identifier) index: (decimal_integer_literal)) index: (decimal_integer_literal)))) right: (identifier)))) (expression_statement (method_invocation object: (field_access object: (identifier) field: (identifier)) name: (identifier) arguments: (argument_list (identifier))))))