description: 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 number 17 is special, because it can be written as 4^0 + 4^2 = 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 10^9+7.
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.
  
  The first and only line of each test case contains two integers n and k (2 ≤ n ≤ 10^9; 1 ≤ k ≤ 10^9).
  
  Output
  
  For each test case, print one integer — the k-th special number in increasing order modulo 10^9+7.
  
  Example
  
  Input
  
  
  3
  3 4
  2 12
  105 564
  
  
  Output
  
  
  9
  12
  3595374
  
  Note
  
  For n = 3 the sequence is [1,3,4,9...]
solution: import java.util.*;
  import java.lang.*;
  import java.io.*;
  /* Name of the class has to be "Main" only if the class is public. */
  public class d2
  {
  	
  	//static ArrayList<ArrayList<Integer>> graph;
  	//static boolean[] visited;
  	//static int[] distance;
  	static long inf = 1_000_000_007;
  	public static void main (String[] args) throws java.lang.Exception
  	{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st = new StringTokenizer(br.readLine());
  		int t = Integer.parseInt(st.nextToken());
  		outer : while(t-->0){
  			st = new StringTokenizer(br.readLine());
  			int n = Integer.parseInt(st.nextToken());
  			int k = Integer.parseInt(st.nextToken());
  			long ans = 0L;
  			long pow = 1L;
              for(int i=0;i<=30;i++){
                   if((k & (1 << i)) > 0){
  					ans = (ans%inf + pow%inf)%inf;
  				 }
  				 pow = (pow*n)%inf;
  			}
  			System.out.println(ans);
  		}
  	}
  		static long gcd(long a,long b){
  			return (b == 0L) ? a : gcd(b,a%b);
  		}
  }
  /*	static void bfs(int vertex,int des,int dist){
  		ArrayDeque<Integer> queue = new ArrayDeque<>();
  		queue.add(vertex);
  		while(!queue.isEmpty()){
            int current = queue.pollFirst();
  		  visited[current] = true;
  		 // System.out.println(current+1);
  		 dist++;
  		  ArrayList<Integer> demo = new ArrayList<>();
  		  for(int v : graph.get(current)){
                 if(!visited[v]){
  				   queue.add(v);
  				   demo.add(v);
  				   if(des == v){
  					   System.out.println("distance = "+dist);
  				   }
  			   }
  		  }
  		  for(int i=0;i<demo.size();i++){
  			  System.out.print((demo.get(i)+1)+" ");
  		  }
  		  if(demo.size() != 0){
  			  System.out.println();
  		  }
  		}
  	}
  	static int gcd(int a,int b){
  		int k = Math.max(a,b);
  		int k1 = Math.min(a,b);
  		return (k1 == 0) ? k : gcd(k1,k%k1);
  	}*/
  