CF1992G Ultra-Meow

K1o0n gave you an array $ a $ of length $ n $ , consisting of numbers $ 1, 2, \ldots, n $ . Accept it? Of course! But what to do with it? Of course, calculate $ \text{MEOW}(a) $ . Let $ \text{MEX}(S, k) $ be the $ k $ -th positive (strictly greater than zero) integer in ascending order that is not present in the set $ S $ . Denote $ \text{MEOW}(a) $ as the sum of $ \text{MEX}(b, |b| + 1) $ , over all distinct subsets $ b $ of the array $ a $ . Examples of $ \text{MEX}(S, k) $ values for sets: - $ \text{MEX}(\{3,2\}, 1) = 1 $ , because $ 1 $ is the first positive integer not present in the set; - $ \text{MEX}(\{4,2,1\}, 2) = 5 $ , because the first two positive integers not present in the set are $ 3 $ and $ 5 $ ; - $ \text{MEX}(\{\}, 4) = 4 $ , because there are no numbers in the empty set, so the first $ 4 $ positive integers not present in it are $ 1, 2, 3, 4 $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. In a single line of each test case, an integer $ n $ ( $ 1 \le n \le 5000 $ ) is entered, the size of the array of gifted numbers. It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 25 \cdot 10^6 $ .

For each test case, output a single number — $ \text{MEOW}(a) $ . Since it may be very large, output it modulo $ 10^9 + 7 $ .