CF2242C Unstable Elements

You are given a sorted array of integers $ [a_1, a_2, \dots, a_n] $ . We can perform any number of operations of the following type on this array: - mark the first element of the array, as well as all elements that are not equal to their left neighbors (that is, all elements $ i $ such that $ a_i \ne a_{i-1} $ ). - then either delete all marked elements or duplicate them (that is, replace each marked element with two identical elements). For example, consider the array $ [\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}] $ (marked elements are shown in bold). If we delete all marked elements, we get $ [1, 1, 4] $ , and if we duplicate them, we get $ [1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5] $ . The operations cannot be performed if the array becomes empty. After each operation, every element gets unmarked. We call an array of integers $ b $ reachable if it can be obtained from array $ a $ by some number of the described operations. Your task is to count the number of reachable arrays of length $ k $ .

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines: - the first line contains two integers $ n $ and $ k $ ( $ 1 \le n, k \le 3 \cdot 10^5 $ ); - the second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_1 \le a_2 \le \dots \le a_n \le n $ ). Note that the array is sorted. Additional constraint on the input: the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output one integer — the number of reachable arrays $ b $ of length $ k $ . It can be shown that, under the constraints of the problem, the answer fits into a standard $ 32 $ -bit integer type.

In the first example, the following sequence of operations can be performed: - $ [\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1] $ . In the second example, it is impossible to obtain an array of length $ 5 $ . In the third example, the following sequence of operations can be performed: - $ [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1] $ . In the fifth example, the arrays $ [1, 1, 2, 2, 2, 2] $ and $ [2, 2, 2, 2, 2, 2] $ can be obtained: - $ [\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2] $ ; - $ [\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2] $ . In the seventh example, the arrays $ [1, 1, 1, 3, 3, 3, 3] $ and $ [3, 3, 3, 3, 3, 3, 3] $ can be obtained.