## Algorithm

B. Special Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of n. For example, for n=4�=4 number 1717 is special, because it can be written as 40+42=1+16=1740+42=1+16=17, but 99 is not.

Theofanis asks you to help him find the k-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo 109+7109+7.

Input

The first line contains a single integer t (1t1041≤�≤104) — the number of test cases.

The first and only line of each test case contains two integers n and k (2n1092≤�≤1091k1091≤�≤109).

Output

For each test case, print one integer — the k-th special number in increasing order modulo 109+7109+7.

Example
input
Copy
3
3 4
2 12
105 564

output
Copy
9
12
3595374

Note

For n=3�=3 the sequence is [1,3,4,9...][1,3,4,9...]

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

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

long long MOD = 1e9 + 7;
#define ll long long
#define ull unsigned long long
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

ull mypow(ull n, ull i) {

ull res = 1;
ull k = n;
while(i--){
res = (res%MOD * k % MOD)%MOD;
}
return (res%MOD);
}

ull binary(ull arr[], ull n){
ull i = 0;
while (n > 0) {
arr[i] = n % 2;
n = n / 2;
i++;
}
return i;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
ull n, k;
while(t--){
cin>>n>>k;
ull ans = 0;

ull s[32];
ull bit = binary(s, k);
for(ull i=0;i< bit;i++){
if(s[i]== 1){
ans = (ans + mypow(n,i)%MOD);
}
}
cout<<(ans%MOD)<<endl;
}
}
Copy The Code &

Input

cmd
3
3 4
2 12
105 564

Output

cmd
9
12
3595374