Little Cyan Fish มีเมทริกซ์ $W$ ขนาด $n \times n$

สำหรับลำดับของจำนวนเต็ม $a_1, a_2, \ldots, a_n$ โดยที่ $1 \le a_i \le n$ ให้ $b_i$ แทนจำนวนของจำนวนเต็มที่แตกต่างกันซึ่งปรากฏมากครั้งที่สุดในอุปสรรค (prefix) $a_1, a_2, \ldots, a_i$ ตัวอย่างเช่น ในอุปสรรค $1, 2, 1, 2, 3$ ทั้ง $1$ และ $2$ ต่างปรากฏสองครั้ง ดังนั้น $b_5 = 2$

Little Cyan Fish นิยามน้ำหนักของลำดับให้เท่ากับ

$$\prod_{i=1}^n w_{i,b_i}.$$

จงหาผลรวมของน้ำหนักของลำดับดังกล่าวทั้งหมด เนื่องจากคำตอบอาจมีค่าใหญ่มาก ให้แสดงผลลัพธ์มอดูโล $998\,244\,353$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งจำนวนคือ $n$ ($1 \le n \le 100$) ซึ่งระบุความยาวของลำดับและขนาดของเมทริกซ์

อีก $n$ บรรทัดถัดไปอธิบายเมทริกซ์ $W$ โดยบรรทัดที่ $i$ ของบรรทัดเหล่านี้ประกอบด้วยจำนวนเต็ม $n$ จำนวนคือ $w_{i,1}, w_{i,2}, \ldots, w_{i,n}$ ($0 \le w_{i,j} < 998\,244\,353$)

ข้อมูลส่งออก

แสดงผลออกทางบรรทัดเดียวซึ่งประกอบด้วยจำนวนเต็มหนึ่งจำนวน ที่ระบุผลรวมของน้ำหนักของลำดับดังกล่าวทั้งหมดมอดูโล $998\,244\,353$

ตัวอย่าง

ข้อมูลนำเข้า 1

1
7

ข้อมูลส่งออก 1

7

ข้อมูลนำเข้า 2

2
1 2
3 4

ข้อมูลส่งออก 2

14

ข้อมูลนำเข้า 3

3
1 1 1
3 1 1
0 0 1

ข้อมูลส่งออก 3

6

หมายเหตุ

ในกรณีทดสอบตัวอย่างแรก ลำดับเดียวที่มีคือ $(1)$ และมีน้ำหนักเป็น $7$

ในกรณีทดสอบตัวอย่างที่สอง ลำดับ $(1, 1)$ และ $(2, 2)$ ต่างมีน้ำหนักเป็น $3$ ในขณะที่ $(1, 2)$ และ $(2, 1)$ ต่างมีน้ำหนักเป็น $4$ ผลรวมคือ $3 + 3 + 4 + 4 = 14$

ในกรณีทดสอบตัวอย่างที่สาม ลำดับจะมีน้ำหนักไม่เป็นศูนย์ก็ต่อเมื่อค่าทั้งสามแตกต่างกันทั้งหมด มีลำดับดังกล่าวหกลำดับ โดยแต่ละลำดับมีน้ำหนักเป็น $1$