B. Special Numbers

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const lli mod = 1e9 + 7;

lli Solve(lli n, lli k){
    lli p = 1, s = 0;
    while(k > 0){
        if(k & 1 == 1)
            s = (s + p) % mod;
        k = k >> 1;
        p = (p * n) % mod;
    }
    return s;
}

int main(){

    int Q;
    scanf("%d", &Q);

    while(Q--){
        lli n, k;
        scanf("%lld%lld", &n, &k);
        printf("%lld\n", Solve(n, k));
    }

    return 0;
}