มีการ์ดอยู่ $U + T + P + C$ ใบ ในจำนวนนี้ มีการ์ด $U$ ใบที่มีรูปยูนิคอร์นอยู่ด้านหน้า, การ์ด $T$ ใบมีรูปเสือ, การ์ด $P$ ใบมีรูปแพนด้า และการ์ด $C$ ใบมีรูปแมว ในตอนเริ่มต้น การ์ดทั้งหมดจะถูกวางคว่ำหน้าลง และไม่สามารถแยกแยะได้ว่าการ์ดแต่ละใบมีรูปอะไร
คุณจะเล่นเกมโดยใช้การ์ดเหล่านี้ เกมประกอบด้วยหลายเทิร์น ในแต่ละเทิร์น คุณสามารถเลือกดำเนินการ การดำเนินการ A หรือ การดำเนินการ B:
- การดำเนินการ A: สุ่มเลือกการ์ดที่คว่ำหน้าอยู่หนึ่งใบด้วยความน่าจะเป็นเท่ากันแล้วหงายขึ้น หากการ์ดที่เปิดได้เป็นรูปยูนิคอร์น เสือ หรือแพนด้า คุณจะเข้าสู่เทิร์นถัดไปและเกมจะดำเนินต่อ การ์ดที่หงายแล้วจะยังคงหงายอยู่เช่นเดิม หากการ์ดที่เปิดได้เป็นรูปแมว เกมจะจบลงทันที ในกรณีนี้ คะแนนของคุณจะเป็น $0$
- การดำเนินการ B: จบเกมทันที ให้ $u$ เป็นจำนวนการ์ดที่หงายอยู่ซึ่งแสดงรูปยูนิคอร์น และ $t$ เป็นจำนวนการ์ดที่หงายอยู่ซึ่งแสดงรูปเสือ คะแนนของคุณจะเป็น $2u + t$
จงหาค่าคาดหมายของคะแนนเมื่อทำตามกลยุทธ์ที่เหมาะสมที่สุดเพื่อทำให้ค่าคาดหมายของคะแนนของคุณมีค่าสูงสุด มอดูโล $998244353$
หมายเหตุเกี่ยวกับค่าคาดหมายมอดูโล $998244353$
สามารถพิสูจน์ได้ว่าค่าคาดหมายในปัญหานี้เป็นจำนวนตรรกยะเสมอ นอกจากนี้ ภายใต้ข้อจำกัดของปัญหานี้ เมื่อเขียนค่าคาดหมายในรูปเศษส่วนอย่างต่ำ $\frac{x}{y}$ รับประกันว่า $y$ ไม่สามารถหารด้วย $998244353$ ลงตัว ดังนั้น จะมีจำนวนเต็ม $z$ ($0 \le z < 998244353$) เพียงค่าเดียวที่ทำให้ $y \cdot z \equiv x \pmod{998244353}$ คุณควรแสดงผลค่า $z$ นี้
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะถูกกำหนดให้จากข้อมูลนำเข้ามาตรฐานในรูปแบบต่อไปนี้:
$$U \quad T \quad P \quad C$$
- ค่าข้อมูลนำเข้าทั้งหมดเป็นจำนวนเต็ม
- $1 \le U, T, P, C \le 10^6$
ข้อมูลส่งออก
พิมพ์คำตอบในบรรทัดเดียว
ตัวอย่าง
ข้อมูลนำเข้า 1
1 1 1 1
ข้อมูลส่งออก 1
166374060
ข้อมูลนำเข้า 2
2 7 1 8
ข้อมูลส่งออก 2
300941313
ข้อมูลนำเข้า 3
20 26 2 14
ข้อมูลส่งออก 3
631490021
หมายเหตุ
- ในตัวอย่างแรก นี่คือหนึ่งในลำดับเหตุการณ์ที่เป็นไปได้ของเกม (โปรดทราบว่านี่ไม่จำเป็นต้องเป็นกลยุทธ์ที่เหมาะสมที่สุด):
- หากคุณดำเนินการ B ในเทิร์นที่ $1$ คะแนนของคุณจะเป็น $0$ และเกมจะจบลง สมมติว่าคุณดำเนินการ A แทน และการ์ดที่หงายขึ้นเป็นรูปยูนิคอร์น
- ในสถานะนี้ หากคุณดำเนินการ B ในเทิร์นที่ $2$ คะแนนของคุณจะเป็น $2$ และเกมจะจบลง สมมติว่าคุณดำเนินการ A แทน และการ์ดที่หงายขึ้นเป็นรูปแพนด้า
- ในสถานะนี้ หากคุณดำเนินการ B ในเทิร์นที่ $3$ คะแนนของคุณจะเป็น $2$ และเกมจะจบลง สมมติว่าคุณดำเนินการ A แทน และการ์ดที่หงายขึ้นเป็นรูปแมว เนื่องจากเปิดได้รูปแมว คะแนนของคุณจึงกลายเป็น $0$ และเกมจบลง
- หากคุณทำตามกลยุทธ์ที่เหมาะสมที่สุด สามารถแสดงได้ว่าค่าคาดหมายของคะแนนคือ $\frac{7}{6}$