MOD = 10**9 + 7 MOD_STR = str(MOD) MOD_LEN = len(MOD_STR) def multiply_by_two(s): result = [] carry = 0 for c in reversed(s): digit = int(c) total = digit * 2 + carry carry = total // 10 result.append(str(total % 10)) if carry > 0: result.append(str(carry)) return ''.join(reversed(result)) def subtract_one(s): digits = list(s) i = len(digits) - 1 while i >= 0 and digits[i] == '0': digits[i] = '9' i -= 1 if i < 0: return '0' digits[i] = str(int(digits[i]) - 1) if digits[0] == '0' and len(digits) > 1: return ''.join(digits).lstrip('0') or '0' return ''.join(digits) def compare_strings(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 is_p_ge_mod(p_str): if len(p_str) > MOD_LEN: return True elif len(p_str) < MOD_LEN: return False else: for i in range(MOD_LEN): p_digit = int(p_str[i]) mod_digit = int(MOD_STR[i]) if p_digit > mod_digit: return True elif p_digit < mod_digit: return False return True def mod_str(s, mod): result = 0 for c in s: result = (result * 10 + int(c)) % mod return result def main(): import sys input = sys.stdin.read().split() T = int(input[0]) idx = 1 for _ in range(T): C_str = input[idx] P_str = input[idx + 1] idx += 2 twoP = multiply_by_two(P_str) twoP_minus_1 = subtract_one(twoP) if not compare_strings(C_str, twoP_minus_1): print(0) continue if is_p_ge_mod(P_str): print(0) continue P_num = int(P_str) C_mod = mod_str(C_str, MOD) P_mod = mod_str(P_str, MOD) k = (C_mod - P_mod + 1) % MOD if k < 0: k += MOD if k < P_num: print(0) continue product = 1 for i in range(P_num): product = product * (k - i) % MOD print(product % MOD) if __name__ == '__main__': main()