#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

// Laske fraktaalin solu annetussa ruudussa
bool get_cell(int64_t row, int64_t col) {
    row++; col++; // Ykkösindeksointi
    int64_t pow2 = 1;
    while(pow2*2 < std::max(row,col)) pow2 *= 2;
    while(row > 1){
        if(col > row) return 0; // Kolmion ulkopuolella 
        if(col > pow2) col -= pow2;
        if(row > pow2) row -= pow2;
        pow2 /= 2;
    }
    return col == 1;
}

int main(){
    int64_t p = 1e9 + 87;
    int64_t q = 1e9 + 21;
    
    // Laske p x p fraktaalin rivien summat
    vector<int64_t> row_sums(p+1);
    row_sums[1] = 1; // Pohjatapaus
    int64_t ans = row_sums[1];
    int64_t prev_pow2 = 1;
    for(int64_t i = 2; i <= p; i++) {
        row_sums[i] = 2*row_sums[i-prev_pow2];
        if(prev_pow2 * 2 <= i) prev_pow2 *= 2;
        ans += row_sums[i];
    }
    
    // Vähennä solut sarakkeesta q eteenpäin
    for(int64_t row = q; row < p; row++) {
        for(int64_t col = q; col < p; col++){
            ans -= get_cell(row,col);
        }
    }
    cout << ans << endl;
}
