Little N เพิ่งได้เรียนรู้เกี่ยวกับ MEX โดย MEX (Minimum Excluded) หมายถึงจำนวนเต็มไม่ติดลบที่น้อยที่สุดที่ไม่ปรากฏในอาเรย์ ตัวอย่างเช่น: $\operatorname{{MEX}}([3, 1, 0]) = 2$, $\operatorname{{MEX}}([2, 2, 1]) = 0$, $\operatorname{{MEX}}([0, 3, 1, 2]) = 4$ ทั้งนี้ Little N นิยามว่าสำหรับอาเรย์ของจำนวนเต็มไม่ติดลบที่มีความยาว $k$ คือ $[b_1, b_2, \dots, b_k]$ หาก $\operatorname{MEX}([b_1, b_2, \dots, b_k]) = k$ แล้ว อาเรย์ $b$ จะเรียกว่าอาเรย์ $k$-ดี

กำหนดจำนวนเต็มบวก $n$ สำหรับอาเรย์ $n$-ดี $p_1, p_2, \dots, p_n$ Little N นิยามฟังก์ชัน $f(p)$ เป็นจำนวนคู่ของจำนวนเต็ม $(l, r)$ ที่สอดคล้องกับเงื่อนไขต่อไปนี้:

• $1 \le l \le r \le n$;
• $p_l, \dots, p_r$ เป็นอาเรย์ $(r - l + 1)$-ดี

Little N ได้พิสูจน์ทฤษฎีบทต่อไปนี้แล้ว: สำหรับอาเรย์ $n$-ดี $p$ ใดๆ จะได้ว่า $1 \le f(p) \le n$ ตอนนี้ Little N หวังว่าคุณจะสามารถหาจำนวนอาเรย์ $n$-ดี $p$ สำหรับแต่ละ $i \in [1, n]$ ที่ทำให้ $f(p) = i$ แน่นอนว่าจำนวนนี้อาจมีค่ามาก ดังนั้นคุณจึงต้องแสดงผลลัพธ์มอดุโล $998\,244\,353$

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

ข้อมูลนำเข้าประกอบด้วยบรรทัดเดียวที่มีจำนวนเต็ม $n$ ($1 \le n \le 10^5$)

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

แสดงผลบรรทัดเดียวที่มีจำนวนเต็ม $n$ จำนวน โดยจำนวนเต็มตัวที่ $i$ แทนจำนวนอาเรย์ $n$-ดี $p$ ที่สอดคล้องกับ $f(p) = i$ มอดุโล $998\,244\,353$

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

1

ข้อมูลส่งออกตัวอย่าง 1

1

ข้อมูลนำเข้าตัวอย่าง 2

3

ข้อมูลส่งออกตัวอย่าง 2

0 2 4

ข้อมูลนำเข้าตัวอย่าง 3

7

ข้อมูลส่งออกตัวอย่าง 3

0 2312 1424 728 352 160 64

หมายเหตุ

สำหรับ $n = 3$ สามารถพิสูจน์ได้ว่ามีอาเรย์ $3$-ดีทั้งหมดหกอาเรย์ โดยมีค่าของฟังก์ชันที่สอดคล้องกันดังนี้:

$f([0, 1, 2]) = 3$, $f([0, 2, 1]) = 2$, $f([1, 0, 2]) = 3$, $f([1, 2, 0]) = 2$, $f([2, 0, 1]) = 3$, $f([2, 1, 0]) = 3$