import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { static Scanner in; static PrintWriter out; static String INPUT = ""; static int dec(char[] a){return dec(a,0,a.length);} static int dec(char[] a,int l,int r){int ret=0;for(int i=r-1;i>=l;i--)ret=ret*93+ord(a[i]);return ret;} static int[] decs(char[] a){int[] ret=new int[a.length/5];for(int i=0,j=0;j= 1;T--){ char[] C = in.next().toCharArray(); char[] P = in.next().toCharArray(); if(P.length >= 11){ out.println(0); continue; } long pl = Long.parseLong(new String(P)); if(pl >= mod){ out.println(0); continue; } long cl = 0; if(C.length >= 12){ for(char x : C)cl = (cl*10+x-'0')%mod; }else{ cl = Long.parseLong(new String(C)); if(cl-(2*pl-1)+1 <= 0){ out.println(0); continue; } } long sup = (cl-(pl-1))%mod; long inf = (cl-(2*pl-1))%mod; if(inf < 0)inf += mod; if(sup < 0)sup += mod; if(sup < inf){ out.println(0); continue; } out.println(f((int)sup)*invl(f((int)inf), mod)%mod); } } public static long invl(long a, long mod) { long b = mod; long p = 1, q = 0; while (b > 0) { long c = a / b; long d; d = a; a = b; b = d % b; d = p; p = q; q = d - c * q; } return p < 0 ? p + mod : p; } static long f(int n) { long mul = fs[n/INTERVAL]; int base = n/INTERVAL*INTERVAL; for(int i = base+1;i <= n;i++){ mul = mul * i % mod; } return mul; } public static void main(String[] args) throws Exception { in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT); out = new PrintWriter(System.out); solve(); out.flush(); } static int ni() { return Integer.parseInt(in.next()); } static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }