CF2150D Attraction Theory

[Taylor Swift - Love Story (Taylor's Version)](https://soundcloud.com/taylorswiftofficial/love-story-taylors-version) ⠀ There are $ n $ people in positions $ p_1, p_2, \ldots, p_n $ on a one-dimensional coordinate axis. Initially, $ p_i = i $ for each $ 1 \leq i \leq n $ . You can introduce an attraction at some integer coordinate $ x $ ( $ 1 \le x \le n $ ), and then all the people will move closer to the attraction to look at it. Formally, if you put an attraction in position $ x $ ( $ 1 \le x \le n $ ), the following changes happen for each person $ i $ ( $ 1 \le i \le n $ ): - if $ p_i = x $ , no change; - if $ p_i < x $ , the person moves in the positive direction, and $ p_i $ is incremented by $ 1 $ ; - if $ p_i > x $ , the person moves in the negative direction, and $ p_i $ is decremented by $ 1 $ . You can put attractions any finite number of times, and in any order you want. It can be proven that all positions of a person always stays within the range $ [1, n] $ , i.e. $ 1 \le p_i \le n $ at all times. Each position $ x $ ( $ 1 \le x \le n $ ), has a value $ a_x $ associated with it. The score of a position array $ [p_1, p_2, \ldots, p_n] $ , denoted by $ score(p) $ , is $ \sum_{i = 1}^{n} a_{p_i} $ , i.e. your score increases by $ a_x $ for every person standing at $ x $ in the end. Over all possible distinct position arrays $ p $ that are possible with placing attractions, find the sum of $ score(p) $ . Since the answer may be large, print it modulo $ 998\,244\,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers — $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single line containing an integer: the sum of $ score(p) $ over all possible distinct position arrays $ p $ that are possible with placing attractions, modulo $ 998\,244\,353 $ .

In the first test case, the only possible result is that person $ 1 $ stays at $ 1 $ . The score of that is $ a_1 = 1 $ . In the second test case, the following position arrays $ [p_1, p_2] $ are possible: - $ [1, 2] $ , score $ 15 $ ; - $ [1, 1] $ , score $ 10 $ ; - $ [2, 2] $ , score $ 20 $ . The sum of scores is $ 15 + 10 + 20 = 45 $ . In the third test case, the following position arrays $ [p_1, p_2, p_3] $ are possible: - $ [1, 1, 1] $ ; - $ [1, 1, 2] $ ; - $ [1, 2, 2] $ ; - $ [1, 2, 3] $ ; - $ [2, 2, 2] $ ; - $ [2, 2, 3] $ ; - $ [2, 3, 3] $ ; - $ [3, 3, 3] $ . Each has a score of $ 3 $ , and thus the total sum is $ 24 $ .