Hoán vị đẹp

Có $n$ thành viên ban giám khảo họp bàn về kỳ thi sắp tới. Thành viên thứ $i$ đã nghĩ ra $a_i$ bài toán và muốn kể lại tất cả cho những người còn lại.

Trước hết, ban giám khảo thống nhất một thứ tự trình bày, tức một hoán vị $p$ của $1,2,\dots ,n$. Buổi họp sau đó diễn ra như sau:

• Nếu thành viên $p_1$ vẫn còn bài chưa kể, họ kể đúng một bài cho cả nhóm. Ngược lại, họ bị bỏ qua.
• Nếu thành viên $p_2$ vẫn còn bài chưa kể, họ kể đúng một bài cho cả nhóm. Ngược lại, họ bị bỏ qua.
• $\dots$
• Nếu thành viên $p_n$ vẫn còn bài chưa kể, họ kể đúng một bài cho cả nhóm. Ngược lại, họ bị bỏ qua.
• Nếu vẫn còn người chưa kể hết bài, quá trình lặp lại từ đầu. Ngược lại, buổi họp kết thúc.

Xét dãy các lượt kể theo đúng thứ tự thời gian của cả buổi họp. Hoán vị $p$ được gọi là đẹp nếu trong dãy đó không có thành viên nào chiếm hai lượt kề nhau. Lưu ý hai lượt kề nhau có thể nằm ở hai vòng khác nhau: người đứng cuối một vòng kể xong rồi lại kể ngay ở đầu vòng sau (vì mọi người khác đều đã hết bài) cũng bị coi là kể hai bài liên tiếp.

Hãy đếm số hoán vị đẹp. Kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $998244353$.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.

Mỗi bộ dữ liệu gồm hai dòng:

• Dòng thứ nhất chứa số nguyên $n$ — số thành viên ban giám khảo.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — số bài toán mỗi thành viên đã nghĩ ra.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số hoán vị đẹp, lấy phần dư khi chia cho $998244353$.

Ràng buộc

• $1\le t\le {10}^4$
• $2\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$

Ví dụ