คุณได้รับจำนวนเต็มบวก $N$ และ $M$
สำหรับแต่ละ $k = 1, 2, \dots, N + M - 1$ ให้ $\text{ans}_k$ แทนคำตอบของปัญหาต่อไปนี้
คู่ของลำดับ $(a, b)$ โดยที่ $a = (a_1, a_2, \dots, a_{N+M-1})$ และ $b = (b_1, b_2, \dots, b_{N+M-1})$ ซึ่งแต่ละลำดับมีความยาว $N + M - 1$ จะเรียกว่า คู่ของลำดับที่ดี ถ้าสอดคล้องกับเงื่อนไขต่อไปนี้ทั้งหมด:
- $(a_1, b_1) = (1, N + 1)$
- สำหรับ $i = 2, 3, \dots, N + M - 1$ ข้อใดข้อหนึ่งต่อไปนี้เป็นจริง:
- $(a_i, b_i) = (a_{i-1} + 1, b_{i-1})$
- $(a_i, b_i) = (a_{i-1}, b_{i-1} + 1)$
- $(a_{N+M-1}, b_{N+M-1}) = (N, N + M)$
สำหรับ คู่ของลำดับที่ดี $(a, b)$ ให้นิยามต้นไม้ $T(a, b)$ ดังนี้:
- เป็นต้นไม้ที่มีจุดยอด $N + M$ จุด โดยมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N + M$
- สำหรับแต่ละ $i = 1, 2, \dots, N + M - 1$ มีเส้นเชื่อมที่เชื่อมระหว่างจุดยอด $a_i$ และจุดยอด $b_i$
สำหรับต้นไม้หนึ่งๆ ให้ $\text{dist}(i, j)$ เป็นจำนวนเส้นเชื่อมบนเส้นทางเชิงเดียวระหว่างจุดยอด $i$ และ $j$ คะแนน ของต้นไม้ถูกนิยามว่าเป็นจำนวนคู่ของจำนวนเต็ม $(i, j)$ ที่ทำให้ $1 \le i < j \le N + M$ และ $\text{dist}(i, j) = k$
จงคำนวณผลรวมของ คะแนน ของ $T(a, b)$ จากทุก คู่ของลำดับที่ดี $(a, b)$ มอดุโล $998244353$
จงคำนวณค่าทั้งหมดของ $\text{ans}_1, \text{ans}_2, \dots, \text{ans}_{N+M-1}$ และแสดงผลลัพธ์ $\sum_{k=1}^{N+M-1} (\text{ans}_k \oplus k)$ โดยที่ $\oplus$ แทนการดำเนินการระดับบิต exclusive OR (XOR)
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะให้มาในรูปแบบต่อไปนี้:
N M
- $1 \le N \le 5 \times 10^6$
- $1 \le M \le 5 \times 10^6$
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
ข้อมูลส่งออก
แสดงคำตอบ
ตัวอย่าง 1
2 2
14
ตัวอย่าง 2
24 167
21925979855
ตัวอย่าง 3
4297614 4167924
4162418864110099
หมายเหตุ
ในตัวอย่างแรก $(\text{ans}_1, \text{ans}_2, \text{ans}_3) = (6, 4, 2)$ ดังนั้น ค่าที่ต้องแสดงผลคือ $(6 \oplus 1) + (4 \oplus 2) + (2 \oplus 3) = 7 + 6 + 1 = 14$