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.*;
  import java.util.*;
  
  public class Main {
  	static int mod=1000000007;
  	static MyScanner sc = new MyScanner();
  	static Output out = new Output();
  
  	public static void main(String[] args) {
  		int t=sc.nextInt();
  		for (int i=0;i<t;i++) {
  			solve();
  		}
  		out.flush();
  	}
  
  	public static void solve() {
  		BigInteger n=new BigInteger(sc.nextInt()+"");
  		BigInteger k=new BigInteger(sc.nextInt()+"");
  		BigInteger ans=new BigInteger(0+"");
  		int i=0;
  		while(!k.equals(new BigInteger("0"))) {
  			BigInteger r=k.mod(new BigInteger("2"));
  			k=k.divide(new BigInteger("2"));
  			if(r.equals(new BigInteger("1")))
  				ans=(ans.add(n.pow(i))).mod(new BigInteger(mod+""));
  			i++;
  		}
  		out.println(ans);
  	}
  }
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  class Array{
  	static void sort(int[] arr){
  		mergesort(arr,0,arr.length-1);
  	}
  	static void sort(int[] arr,int startIndex,int endIndex){
  		mergesort(arr,startIndex,endIndex);
  	}
  
  	static void mergesort(int[] arr,int b,int e) {
  		if(b<e) {
  			int m=b+(e-b)/2;
  			mergesort(arr,b,m);
  			mergesort(arr,m+1,e);
  			merge(arr,b,m,e);
  		}
  		return;	
  	}
  	static void merge(int[] arr,int b,int m,int e) {
  		int len1=m-b+1,len2=e-m;
  		int[] l=new int[len1];
  		int[] r=new int[len2];
  		for(int i=0;i<len1;i++)l[i]=arr[b+i];
  		for(int i=0;i<len2;i++)r[i]=arr[m+1+i];
  		int i=0,j=0,k=b;
  		while(i<len1 && j<len2) {
  			if(l[i]<r[j])arr[k++]=l[i++];
  			else arr[k++]=r[j++];
  		}
  		while(i<len1)arr[k++]=l[i++];
  		while(j<len2)arr[k++]=r[j++];
  		return;
  	}
  	
  }
  class MyScanner {
  
  	BufferedReader br;
  	StringTokenizer st;
  
  	public MyScanner() {
  		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());
  	}
  
  	String nextLine() {
  		String str = "";
  		try {
  			str = br.readLine();
  		} catch (IOException e) {
  			e.printStackTrace();
  		}
  		return str;
  	}
  
  	public int[] nextIntArr(int n) {
  		int a[] = new int[n];
  		for (int i = 0; i < n; i++)
  			a[i] = nextInt();
  		return a;
  	}
  
  	public long[] nextLongArr(int n) {
  		long a[] = new long[n];
  		for (int i = 0; i < n; i++)
  			a[i] = nextLong();
  		return a;
  	}
  
  	public double[] nextDoubleArr(int n) {
  		double a[] = new double[n];
  		for (int i = 0; i < n; i++)
  			a[i] = nextDouble();
  		return a;
  	}
  
  	public String[] nextArr(int n) {
  		String a[] = new String[n];
  		for (int i = 0; i < n; i++)
  			a[i] = next();
  		return a;
  	}
  
  	public String[] nextLineArr(int n) {
  		String a[] = new String[n];
  		for (int i = 0; i < n; i++)
  			a[i] = nextLine();
  		return a;
  	}
  }
  
  class Output {
  	BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  	public void print() {}
  	public void println() {
  		try {
  			out.write("\n");
  		} catch (Exception e) {}
  	}
  	public void print(Object s) {
  		try {
  			out.write(s + "");
  		} catch (Exception e) {}
  	}
  	public void println(Object s) {
  		try {
  			out.write(s + "\n");
  		} catch (Exception e) {}
  	}
  	public void flush() {
  		try {
  			out.flush();
  		} catch (Exception e) {}
  	}
  }