Description

Given the sequence a[0 . . . n] ,ask the value of $$ \sum_{i=0}^{n} \sum_{j=0}^{ai}{P（ij）} $$ mod 998241383

wikipedia: k-permutations of n are the different ordered arrangements of a k-element subset of an n-set (sometimes called variations or arrangements in the older literature). These objects are also known as partial permutations or as sequences without repetition, terms that avoid confusion with the other, more common, meaning of ”permutation”. The number of such k-permutations of n is denoted variously by such symbols as Pkn or P(n, k),and its value is given by the product P(n, k) = n · (n − 1) · (n − 2)· · ·(n − k + 1) | {z } k factors ,which is 0 when k > n, and otherwise is equal to n! (n−k)! .

Assume that P(i, 0) = 1, P(0, 0) = 1

Input

The first line contains an integer T(T ≤ 3) — the number of test cases you need to solve. The first line of each test case contains an integer n(1 ≤ n ≤ 10⁵). The second line contains n space-separated integers a0, a1, · · · , an(0 ≤ ai ≤ i) — the elements of the array a.

Output

For each test case, print the result mod naughty 998241383

1
5
0 1 1 3 2 4

245