คุณมีลำดับที่ประกอบด้วยเลข $1$ และ $2$ ในแต่ละขั้น คุณสามารถ:
- แทรก $1$ ในตำแหน่งที่อยู่ทางขวาของ $1$ ตัวอื่นทั้งหมด (หรือแทรกที่ใดก็ได้หากไม่มี $1$)
- เปลี่ยน $2$ ตัวใดก็ได้เป็น $1$ หากไม่มี $1$ อยู่ทางขวาของ $2$ ตัวนั้น
- ลบ $1$ ที่อยู่ขวาสุด (สังเกตว่าการดำเนินการนี้เป็นการย้อนกลับของการดำเนินการที่ 1)
- เปลี่ยน $1$ ที่อยู่ขวาสุดเป็น $2$ (สังเกตว่าการดำเนินการนี้เป็นการย้อนกลับของการดำเนินการที่ 2)
ตัวอย่างเช่น จากลำดับ $11212122$ คุณสามารถได้ลำดับต่อไปนี้ในหนึ่งขั้น:
- ด้วยการดำเนินการที่ 1: $112121122$, $112121212$, $112121221$
- ด้วยการดำเนินการที่ 2: $11212112$, $11212121$
- ด้วยการดำเนินการที่ 3: $1121222$
- ด้วยการดำเนินการที่ 4: $11212222$
หน้าที่ของคุณคือคำนวณจำนวนวิธีเปลี่ยนลำดับที่ประกอบด้วยเลข $2$ จำนวน $a$ ตัวพอดี ให้เป็นลำดับที่ประกอบด้วยเลข $2$ จำนวน $b$ ตัวพอดี โดยใช้การดำเนินการจำนวน $t$ ครั้งพอดี
ข้อมูลนำเข้า
ข้อมูลนำเข้ามีเพียงบรรทัดเดียว ประกอบด้วยจำนวนเต็มสามจำนวน $a$, $b$ และ $t$ ($0 \le a,b,t \le 10^6$)
ข้อมูลส่งออก
พิมพ์จำนวนวิธีที่ทำให้ได้ลำดับของเลข $2$ จำนวน $b$ ตัวจากลำดับของเลข $2$ จำนวน $a$ ตัว ในจำนวน $t$ ขั้นพอดี เนื่องจากจำนวนนี้อาจมีค่ามาก ให้พิมพ์เศษจากการหารด้วยจำนวนเฉพาะ $998\,244\,353$
ตัวอย่าง
ข้อมูลนำเข้า 1
0 0 4
ข้อมูลส่งออก 1
3
ข้อมูลนำเข้า 2
1 4 6
ข้อมูลส่งออก 2
60
หมายเหตุ
ในตัวอย่างแรก คุณต้องเปลี่ยนลำดับว่างให้เป็นลำดับว่างใน 4 ขั้น วิธีทำมีดังนี้ ($\varepsilon$ แทนลำดับว่าง):
$$ \varepsilon \to 1 \to \varepsilon \to 1 \to \varepsilon $$
$$ \varepsilon \to 1 \to 11 \to 1 \to \varepsilon $$
$$ \varepsilon \to 1 \to 2 \to 1 \to \varepsilon $$