Special Numbers Codeforces Solution

Introduction

Codeforces organizes many contests out of which one is this Codeforces rounds to improve coding skills and get a higher coding knowledge. Codeforces Round 747 Div 2 was too a great round to test our coding skills. This round was held on  Friday, October 8, 2021 at 20:35UTC+5.5. This round will be rated for coders with rating upto 2100. A total of 6 problems are given which needs to be solved in 2 hours 15 minutes.  

The first problem that is Consecutive Sum  Riddle was cakewalk it was so simple that in 5 minutes we had more that four thousand successful submissions. Problem B was too a great deal of simplicity but it took a bit of time to understand what to do in the problem. Problem C was medium level and was a good question of logic for the average coders and for best coders it was just too simple. Problem D was good to go but the question was quite difficult to guess what algorithm would be required. Problem E1 was quite simple and many successful submissions were made. Problem E2 and F were the testing the skills of top coders and average coders just kept guessing what algorithms to use.

The contest was a great success and every body enjoyed it truly. Just practice more questions and go ahead in building a streak of code and get better everyday. Happy coding journey ahead. 

Question

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=4number 17is special, because it can be written as 40+42=1+16=17, but 9 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+7

Input

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

The first and only line of each test case contains two integers n$n$ and k$k$ (2≤n≤109; 1≤k≤109).

Output

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

Example

input

Copy

3
3 4
2 12
105 564

output

Copy

9
12
3595374

Explanation

The problem is quite simple you just need to think of numbers with their base of n that is numbers with base n. The problem is same as finding k-th number that in base n has only zeroes and ones. So you can write k in binary system instead of powers of 2, add powers of n. This the main logic behind the code given below we just calculate in power function all the work to be done. Don't use normal pow function since it will create errors in powers of large values and may give Time Limit Exceeded error also. Then we just add the powers to get our answer. That's it the problem was this simple. I recommend to do the solution by your own logic then see the code given below if you are stuck doing this. This will improve your coding and logical skills.

Program Code in C++

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

ll m=1000000007;

ll power(ll x, unsigned int y, ll p)

{

    ll res = 1;     

 

    x = x % p; 

  

    if (x == 0) return 0; 

 

    while (y > 0)

    {

        

        if (y & 1)

            res = (res*x) % p;

 

        y = y>>1; 

        x = (x*x) % p;

    }

    return res;

}

int main(){

    ios_base::sync_with_stdio(false);

    ll t;

    cin>>t;

   while(t--){

      ll n,k;

      cin>>n>>k;

      ll ans=0;

      ll p=0;

      while(k>0){

      ll r=k%2;

      if(r==1){

      ans+=power(n,p,m);

      ans=ans%m;

   }

   p++;

   k=k/2;

  }

  cout<<ans<<endl;

    }

    

    return 0;

}

This is the end of solution hope you enjoyed it and got benefit from it and made your journey of coding smooth.