B'This is the hard version of the problem. The differences between the two versions are the constraints on n, m, b_0 and the time limit. You can make hacks only if both versions are solved. Little R has counted many sets before, and now she decides to count arrays. Little R thinks an array b_0, ldots, b_n consisting of non-negative integers is continuous if and only if, for each i such that 1 <= q i <= q n , lvert b_i - b_{i-1} rvert = 1 is satisfied. She likes continuity, so she only wants to generate continuous arrays. If Little R is given b_0 and a_1, ldots, a_n , she will try to generate a non-negative continuous array b , which has no similarity with a . More formally, for all 1 <= q i <= q n , a_i neq b_i holds. However, Little R does not have any array a . Instead, she gives you n , m and b_0 . She wants to count the different integer arrays a_1, ldots, a_n satisfying: Note that b_i geq 0 , but the b_i can be arbitrarily large. Since the actual answer may be enormous, please just tell her the answer modulo 998 ,244 ,353 . Each test contains multiple test cases. The first line contains the number of test cases t (1 <= q t <= q 10^4) . The description of the test cases follows. The first and only line of each test case contains three integers n , m , and b_0 ( 1 <= q n <= q 2 cdot 10^6 , 1 <= q m <= q 2 cdot 10^6 , 0 <= q b_0 <= q 2 cdot 10^6 ) -- the length of the array a_1, ldots, a_n , the maximum possible element in a_1, ldots, a_n , and the initial element of the array b_0, ldots, b_n . It is guaranteed that the sum of n over all test cases does not exceeds 10^7 . For each test case, output a single line containing an integer: the number of different arrays a_1, ldots, a_n satisfying the conditions, modulo 998 ,244 ,353 . In the first test case, for example, w'...