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.io.*;
  import java.math.BigInteger;
  import java.util.*;
  
  public class P03 {
      
  	static class FastReader{
  		BufferedReader br ;
  		StringTokenizer st;
  		public FastReader() {
  			br = new BufferedReader(new InputStreamReader(System.in));
  			
  		}
  		String next() {
  			while(st==null || !st.hasMoreElements()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				}catch(IOException e) {
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
  		
  		int nextInt() {
  			return Integer.parseInt(next());
  		}
  		
  		long nextLong() {
  			return  Long.parseLong(next());
  		}
  		
  		double nextDouble() {
  			return Double.parseDouble(next());
  		}
  		
  		float nextFloat() {
  			return Float.parseFloat(next());
  		}
  		String nextLine() {
  			String str = "";
  			try {
  				str = br.readLine();
  			}catch(IOException e) {
  				e.printStackTrace();
  			}
  			return str ;
  		}
  	}
  	
  	private static long gcd(long l, long m) {
  		// TODO Auto-generated method stub
  		if(m==0) {
  			return l;
  		}
  		return gcd(m,l%m);
  	}
  	static void swap(long[] arr, int i, int j)
  	{
  	    long temp = arr[i];
  	    arr[i] = arr[j];
  	    arr[j] = temp;
  	}
  
  	static int partition(long[] arr, int low, int high)
  	{	   
  	    long pivot = arr[high];   
  	    int i = (low - 1);
  	    for(int j = low; j <= high - 1; j++)
  	    {    
  	        if (arr[j] < pivot)
  	        {          
  	            i++;
  	            swap(arr, i, j);
  	        }
  	    }
  	    swap(arr, i + 1, high);
  	    return (i + 1);
  	}
  	static void quickSort(long[] arr, int low, int high)
  	{
  	    if (low < high)
  	    {  
  	        int pi = partition(arr, low, high);
  	        quickSort(arr, low, pi - 1);
  	        quickSort(arr, pi + 1, high);
  	    }
  	}
  	static long M = 1000000007;
  	static long powe(long a,long b) {
  		long res =1;
  		while(b>0) {
  			if((b&1)!=0) {
  				res=(res*a)&M;
  			}
  			a=(a*a)%M;
  			b>>=1;
  		}
  		return res;
  	}
  	static long power(long x, long y, long p)  {
  	    long res = 1; 	 
  	    x = x % p; 	 
  	    if (x == 0)
  	      return 0; 	 
  	    while (y > 0)
  	    {	 	      
  	      if ((y & 1) != 0)
  	      res = (res * x) % p;	 	    
  	      y = y >> 1; 
  	      x = (x * x) % p;
  	    }
  	    return res;
  	  }
  	static boolean [] seive(int n) {
  		boolean a[] = new boolean[n+1];
  		Arrays.fill(a, true);
  		a[0]=false;
  		a[1]=false;
  		for(int i =2;i<=Math.sqrt(n);i++) {
  			for(int j =2*i;j<=n;j+=i) {
  				a[j]=false;
  			}
  		}
  		
  		return a;
  	}
  	
  	static //MAIN FUNCTION ------->
  	 ArrayList<String> alpos = new ArrayList<>();
  	public static void main(String[] args) throws IOException {
  		FastReader fs = new FastReader();
  		Scanner sc = new Scanner (System.in);
  		int t = fs.nextInt();
  		while(t-->0) {
  			long n = fs.nextLong();
  			long k = fs.nextLong();
  			long  m = 1000000007;
  			long ans =0;
  			while(k>0) {
  				if(k==1) {
  					ans+=1;
  					break;
  				}
  				
  				long x = (long) (Math.log10(k)/Math.log10(2));
  				ans=((ans%m)+(power(n,x,m)%m))%m;
  			//	System.out.println(k+" "+x+" "+ans);
  				k-=Math.pow(2, x);
  				
  			}
  			System.out.println(ans);
  		}  
  	}
  	private static void pa(int[] a) {
  		for(int i =0;i<a.length;i++) {
  			System.out.print(a[i]+" ");
  		}
  		System.out.println();
  		
  	}
  	private static String xor(String x, String ans) {
  		String an ="";
  		for(int i =0;i<x.length();i++) {
  			int s1  = (x.charAt(i)-'0')^ (ans.charAt(i)-'0');
  			an+=Integer.toString(s1);	
  		}
  		return an;
  	}
  }
  
  
  
  