MOD = 10**9 + 7 MOD_str = '1000000007' def double(s): res = [] carry = 0 for c in reversed(s): d = int(c) product = d * 2 + carry carry = product // 10 res.append(product % 10) if carry > 0: res.append(carry) res = res[::-1] return ''.join(map(str, res)) if res else '0' def subtract_one(s): s_list = list(s) i = len(s_list) - 1 while i >= 0: if s_list[i] == '0': s_list[i] = '9' i -= 1 else: s_list[i] = str(int(s_list[i]) - 1) break if len(s_list) == 0: return '0' if s_list[0] == '0' and len(s_list) > 1: s_list = s_list[1:] return ''.join(s_list) if s_list else '0' def is_ge(a, b): if len(a) > len(b): return True elif len(a) < len(b): return False else: for i in range(len(a)): if a[i] > b[i]: return True elif a[i] < b[i]: return False return True def compute_mod(s, mod): result = 0 for c in s: result = (result * 10 + int(c)) % mod return result T = int(input()) for _ in range(T): C, P = input().split() # Check if P >= MOD p_ge = False if len(P) > len(MOD_str): p_ge = True elif len(P) == len(MOD_str): for i in range(len(P)): if P[i] > MOD_str[i]: p_ge = True break elif P[i] < MOD_str[i]: break else: p_ge = True if p_ge: print(0) continue # Compute 2P -1 double_p = double(P) two_p_minus_1 = subtract_one(double_p) if not is_ge(C, two_p_minus_1): print(0) continue # Compute mod_c and mod_p mod_c = compute_mod(C, MOD) mod_p = compute_mod(P, MOD) k = int(P) # Compute combination(n, k) mod MOD result = 1 for i in range(1, k+1): term = (mod_c - 2 * mod_p + 1 + i) % MOD term = (term + MOD) % MOD # Ensure it's positive inv_i = pow(i, MOD-2, MOD) result = (result * term) % MOD result = (result * inv_i) % MOD # Compute P! mod MOD fact_p = 1 for i in range(1, k+1): fact_p = (fact_p * i) % MOD total = (result * fact_p) % MOD print(total)