1594B

#include <bits/stdc++.h>
using namespace std;

const long long m = 1e9 + 7;

long long power(long long a, long long b){
    long long s = 1;
    for(long long i = 1; i <= b; i++){
        s *= (a % m) % m;
    }
    return s;
}

void solve() {
    long long int n,k,pos=0;
    long long sum=0;
    vector <long long> v;
    cin >> n >> k;
    while(k) {
        if(k & 1) v.push_back(pos);
        k >>= 1;
        pos++;
    }
    //for(int i=0 ; i<v.size() ; i++) cout << v[i] << " ";
    for(int i=0 ; i<v.size() ; i++) {
        sum += (power(n,v[i]) % (long long)(1e9+7));
    }
    cout << sum << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    //cout << power(4,3);
}