Algorithm

B. Special Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1594/B
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� (1≤t≤1041≤�≤104) — the number of test cases.

The first and only line of each test case contains two integers n� and k� (2≤n≤1092≤�≤109; 1≤k≤1091≤�≤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 & Try With Live Editor

Input

x
–
+
cmd
3
3 4
2 12
105 564

Output

x
–
+
cmd
9
12
3595374
Advertisements

Demonstration

Codeforcess Solution 1594-B B. Special Numbers ,C++, Java, Js and Python ,1594-B,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+