CF2171G Sakura Adachi and Optimal Sequences

"What a pain..." — Hougetsu Shimamura Adachi is in the middle of a generational crashout... over, uh, this problem! Yep, that's definitely it... anyways, please help her solve it! You are given two arrays $ a $ and $ b $ of length $ n $ ( $ 1\leq a_i\leq b_i $ ). In one operation, you may either: - choose an index $ i $ ( $ 1\leq i\leq n $ ) and set $ a_i := a_i + 1 $ , or - double all elements of $ a $ . Let $ x $ denote the minimum number of operations needed to make $ a = b $ . Two arrays $ a $ and $ b $ of length $ n $ are considered equal if $ a_i = b_i $ for all $ 1\leq i\leq n $ . Find the value of $ x $ . Additionally, count the number of sequences of operations that make $ a = b $ using exactly $ x $ operations. Two such sequences of operations are considered different if, for any $ 1\leq j\leq x $ , the $ j $ -th operation of each sequence differs (either in the type of operation selected or the index chosen, if applicable). Since the number of sequences may be large, output it modulo $ {\color{red}{10^6+3}} $ . Note that $ 10^6+3 $ is a prime number.

The first line contains a single integer $ t $ ( $ 1\leq t\leq 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2\leq n\leq 2\cdot 10^5 $ ). The second line of each test case contains $ n $ integers, $ a_1, a_2, \dots, a_n $ ( $ 1\leq a_i\leq 10^6 $ ). The third line of each test case contains $ n $ integers, $ b_1, b_2, \dots, b_n $ ( $ a_i\leq b_i\leq 10^6 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, output two integers, the value of $ x $ , and the number of sequences of operations that make $ a = b $ using exactly $ x $ operations, modulo $ 10^6+3 $ . The value of $ x $ should be printed exactly; that is, it should not be taken modulo $ 10^6 + 3 $ .

In the second sample, it is possible to convert $ a $ into $ b $ using only three operations. There is only one way to do so, namely: - Add $ 1 $ to $ a_1 $ , yielding $ a = [2, 1] $ . Then double all elements of $ a $ , yielding $ a = [4, 2] $ . Then add $ 1 $ to $ a_2 $ , yielding $ a = [4, 3] $ . Then we have that $ a = b $ , as desired. It can be shown that it is impossible to convert $ a $ into $ b $ using fewer than three operations.