F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

YJC plays Minecraft

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 524288/262144 K (Java/Others)
Total Submission(s): 396    Accepted Submission(s): 248


Problem Description
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,1\leq {a}_{i}\leq 100000$
 

Output
For each test:

One line, one integer, the answer modulo $998244353$.
 

Sample Input
1 3 3 3 3
 

Sample Output
2680
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-31 06:59:13, Gzip enabled