Fox Ciel studies number theory.

She thinks a non-empty set S contains non-negative integers is perfect if and only if for any <image> (a can be equal to b), <image>. Where operation xor means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than k. The answer can be very large, so print it modulo 1000000007 (109 + 7).

Input

The first line contains an integer k (0 ≤ k ≤ 109).

Output

Print a single integer — the number of required sets modulo 1000000007 (109 + 7).

Examples

Input

1


Output

2


Input

2


Output

3


Input

3


Output

5


Input

4


Output

6

Note

In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero.

In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 3}.
import java.io.*;
import java.lang.*;
import static java.lang.Math.max;
import static java.lang.Math.pow;
import java.lang.reflect.*;
import java.math.BigInteger;
import static java.math.BigInteger.*;
import java.security.CodeSource;
import java.security.KeyStore;
import java.util.*;
import static java.util.Arrays.*;
import java.util.jar.JarEntry;
import java.util.jar.JarFile;
import java.util.logging.Level;
import java.util.logging.Logger;

// https://netbeans.org/kb/73/java/editor-codereference_ru.html#display

public class Main {

    private void run() throws Exception {
        err = System.err;
        boolean oj = true;
        try {
            oj = System.getProperty("MYLOCAL") == null;
        } catch (Exception e) {
        }
        
        if( oj ){
            sc = new FastScanner(new InputStreamReader(System.in));
            out = new PrintWriter(new OutputStreamWriter(System.out));
        }
        else{
            try {
                sc = new FastScanner(new FileReader("input.txt"));
                out = new PrintWriter(new FileWriter("output.txt"));
            } catch ( IOException e) {
                MLE();
            }
        }
        solve();
        
        out.flush();
    }
    
    FastScanner sc;
    PrintWriter out;
    PrintStream err;
    
    
    void MLE(){
        int[][] arr = new int[1024*1024][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[1024*1024];
        }
    }

    private int getBit(int msk, int pos) {
        return (msk >> pos) & 1;
    }

    class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStreamReader reader) {
            br = new BufferedReader(reader);
            st = new StringTokenizer("");
        }

        String next() {
            while( !st.hasMoreElements() )
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException ex) {
                    MLE();
                }
            return st.nextToken();
        }
        
        int nextInt(){ return Integer.parseInt(next());}
    }

    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    //-------------------------------------------------------------------//
   
    
    final long mod = (long)1e9 + 7;
    int n;
    
    void solve(){
//        int p = 5;
//        out.println( new BF((1<<p)-1).bf() );
//        out.println( cleaver(p) );
//        out.println( getDP(0,p-1) );
        
        {
            n = sc.nextInt();
            int p = 31 - Integer.numberOfLeadingZeros(n);
            out.println( getAns(0,p) );
        }

        
//        for( n = 1; n <= 15; ++n ){
//            int p = 31 - Integer.numberOfLeadingZeros(n);
//            out.println( getAns(0,p) );
//        
//            out.println( new BF(n).bf() );
//            out.println();
//            out.flush();
//            
//        }
    }
    
//    long getAns( int cntOnes, int pos ){
//        if( pos == -1 ) return 1;
//        
//        long ans = 0;
//        if( getBit(n,pos) == 1 ){
//            ans += getDP( cntOnes, pos - 1);
//            ans += getAns( cntOnes+1, pos - 1);
//            ans += getAns( cntOnes, pos - 1) * ( (1<<cntOnes) - 1 );
//        }
//        else{
//            ans += getAns( cntOnes, pos - 1);
//        }
//        err.printf( "%d %d %d\n", cntOnes, pos, ans );
//        return ans;
//    }
   
    long[][] getAns = new long[100][100];
    long[][] getDP = new long[100][100];
    {
        for (long[] ls : getAns) fill( ls, -1 );
        for (long[] ls : getDP ) fill( ls, -1 );
    }
    
    long getAns( int cntOnes, int pos ){
        if( pos == -1 ) return 1;
        
        if( getAns[cntOnes][pos] != -1 ) return getAns[cntOnes][pos];
        
        long ans = 0;
        // add vector
        if( getBit(n,pos) == 1 ){
            ans += getAns( cntOnes+1, pos - 1);
        }
        
        // don't add vector
        if( cntOnes == 0 ){
            if( getBit(n,pos) == 1 )
                ans += getDP( cntOnes, pos - 1 );
            else
                ans += getAns( cntOnes, pos - 1 );
        }
        else{
            if( getBit(n,pos) == 1 ){
                // set 0
                ans += getDP( cntOnes, pos - 1) * (1<<(cntOnes-1)) % mod;
                // set 1
                ans += getAns( cntOnes, pos - 1) * (1<<(cntOnes-1)) % mod;
            }
            else{
                // set 0
                ans += getAns( cntOnes, pos - 1) * (1<<(cntOnes-1)) % mod;
            }
        }
        err.printf( "%d %d %d\n", cntOnes, pos, ans );
        return getAns[cntOnes][pos] = ans % mod;
    }
  
    long getDP( int cntOnes, int pos ){
        if( pos == -1 ) return 1;
        
        if( getDP[cntOnes][pos] != -1 ) return getDP[cntOnes][pos];
        long ans = 0;
        ans += getDP( cntOnes+1, pos - 1);
        ans += getDP( cntOnes, pos - 1) * (1<<cntOnes) % mod;
        return getDP[cntOnes][pos] = ans % mod;
    }
    
}
