E. Pre-minimum Score
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Give you some integral numbers $$$∈[1,n]$$$.The frequency of number $$$i$$$ is $$$m_i$$$.Now let's consider a sequence $$$a$$$ formed by these numbers.

Define the score of $$$a$$$ as $$$f(a)=\Pi x(∃i,min(a_1,a_2,...,a_i)=x)$$$

In other words,$$$f(a)$$$ is the product of all different prefix minimum values of $$$a$$$.

For example,$$$a=[4,4,2,3,1],f(a)=4*2*1=8$$$.

For all different possible sequences $$$a$$$,calculate:$$$\Sigma f(a)$$$ modulo $$$998244353$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains an integer $$$n(1 \leq n \leq 10^6)$$$.

The next lines contains $$$n$$$ space-separated integers:$$$m_1$$$,$$$m_2$$$,...$$$m_n$$$ $$$(1 \leq m_i \leq 10^7)$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.

The sum of $$$m_i$$$ over all test cases won't exceed $$$10^7$$$.

Output

For each test case, output on a new line — $$$Σf(a)$$$ modulo $$$998244353$$$ for all different possible sequences $$$a$$$.

Example
Input
2
3
1 2 1
8
22132 99819 132890 139000 2321 493 2029 2339
Output
30
365519545
Note

Test case $$$1$$$:All possible sequences are as follows:

  1. $$$a=[1,2,2,3],f(a)=1$$$;
  2. $$$a=[1,2,3,2],f(a)=1$$$;
  3. $$$a=[1,3,2,2],f(a)=1$$$;
  4. $$$a=[2,1,2,3],f(a)=2$$$;
  5. $$$a=[2,1,3,2],f(a)=2$$$;
  6. $$$a=[2,2,1,3],f(a)=2$$$;
  7. $$$a=[2,2,3,1],f(a)=2$$$;
  8. $$$a=[2,3,1,2],f(a)=2$$$;
  9. $$$a=[2,3,2,1],f(a)=2$$$;
  10. $$$a=[3,1,2,2],f(a)=3$$$;
  11. $$$a=[3,2,1,2],f(a)=6$$$;
  12. $$$a=[3,2,2,1],f(a)=6$$$;

$$$\Sigma f(a)=1+1+1+2+2+2+2+2+2+3+6+6=30$$$.