If you need a structure for modular numbers, here is my:

const int MOD = 1e9 + 7;

struct Number {
    int value;
    Number (int value) {
        this->value = (MOD + value) % MOD;
    }

    friend bool operator< (const Number& a, const Number& b) {
        return a.value < b.value;
    }

    friend bool operator== (const Number& a, const Number& b) {
        return a.value == b.value;
    }

    friend Number operator+ (const Number& a, const Number& b) {
        return Number ((a.value + b.value) % MOD);
    }

    friend Number operator- (const Number& a, const Number& b) {
        return Number ((a.value - b.value + MOD) % MOD);
    }

    friend Number operator* (const Number& a, const Number& b) {
        return Number (int(1LL * a.value * b.value % MOD));
    }

    friend Number operator^ (const Number& a, const Number& k) {
        if (k == 0) return 1;
        if (k == 1) return a;
        Number res = a ^ Number (k.value/2);
        return res * res * Number(k.value%2);
    }


    Number (int a, int k) {
        if (k == 0) this->value = 1;
        else if (k == 1) this->value = a;
        else {
            Number res = Number (a, k/2);
            res = res * res * Number(a, k%2);
            this->value = res.value;
        }
    }

    friend Number operator/ (const Number& a, const Number& b) {
        return a * Number(b.value, MOD - 2);
    }

    friend ostream& operator<<(ostream& os, const Number& a) {
        os << a.value;
        return os;
    }
};

There is new method of binary search which may be exist but I didn't see it.

Instead of using left and right, we can simply add new bit to our answer if it is possible:

while bit > 0:
   if check(ans + bit): 
      ans += bit
   bit /= 2

Constant will be much smaller.