YJC is an old driver of mini train. Today when he was playing his favorite game Minecraft, he found $n$ islands. YJC numbered them $1$...$n$, and on the $i$th island, there are ${a}_{i}$ cities. Every two cities on the same island are connected directly by a road. Also, the ${a}_{i}$th city on the $i$th island and the $1$th city on the $i+1$th island are connected by an underwater railway. ($1\leq i< n$) Specially, the ${a}_{n}$th city on the $n$th island and the $1$th city on the $1$th island are connected by an underwater railway.
YJC decides to pull down some of the roads and railways, making every two cities connected directly or indirectly by at most one unique route or not connected at all. Now YJC wants to know how many ways there are to reach his goal. The answer can be huge, so output the answer modulo $998244353$.
Input
Multiple tests.
The first line one integer T, indicating the number of cases.
For each test:
The first line one integer $n$, indicating the number of islands.
Next $n$ lines, in each line there is one integer ${a}_{i}$.
$1\leq T\leq 5,n\leq 100000,2\leq {a}_{i}\leq 100000$
Output
For each test:
One line, one integer, the answer modulo $998244353$.
