มีสตริงฐานสอง $s_1$ ความยาว $m$ เก็บอยู่บนดิสก์หมายเลข #1
จากนั้นจะมีการดำเนินการ $n - 1$ ครั้ง ในการดำเนินการครั้งที่ $i$ จะเลือกดิสก์ $1 \le p_{i+1} \le i$ มาหนึ่งดิสก์ แล้วคัดลอกสตริง $s_{p_{i+1}}$ บนดิสก์นั้นไปยังดิสก์ $i + 1$ ได้เป็นสตริง $s_{i+1}$ อย่างไรก็ตาม ในระหว่างกระบวนการคัดลอก อาจมีบิตถูกพลิกได้ไม่เกิน $k$ บิต (กล่าวคือ เกิดข้อผิดพลาดได้ไม่เกิน $k$ ตำแหน่ง)
คุณจะได้รับสตริงฐานสองสุดท้ายทั้งหมด $n$ สตริง คือ $s_1, s_2, \dots, s_n$ ซึ่งแต่ละสตริงมีความยาว $m$ งานของคุณคือการหาว่ามีลำดับ $p_2, p_3, \dots, p_n$ ที่เป็นไปได้ทั้งหมดกี่ลำดับที่สามารถทำให้เกิดผลลัพธ์สุดท้ายนี้ได้
เนื่องจากคำตอบอาจมีค่ามาก คุณจึงต้องหาคำตอบมอดูโล $998244353$ เท่านั้น
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสามจำนวน $n, m, k$ ($2 \le n \le 5000, 4 \le m \le 15000, 1 \le k \le 3$) ตามที่อธิบายไว้ในโจทย์ รับประกันว่า $m$ เป็นพหุคูณของ $4$
ใน $n$ บรรทัดถัดไป แต่ละบรรทัดประกอบด้วยสตริงเลขฐานสิบหก $s'_i$ ความยาว $m/4$ อักขระแต่ละตัวของ $s'_i$ จะเป็นหนึ่งใน 0–9 หรือ A–F โดยที่ $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$
แต่ละหลักในการแทนด้วยเลขฐานสิบหก $s'_i$ จะสอดคล้องกับสี่บิตที่อยู่ติดกันในสตริงฐานสอง $s_i$ กล่าวโดยเจาะจงคือ สำหรับแต่ละหลัก $s'_{i,j}$ สามารถพิสูจน์ได้ว่ามีทูเพิล $(a, b, c, d)$ เพียงชุดเดียวที่สอดคล้องกับ $s'_{i,j} = 8a + 4b + 2c + d$ และ $a, b, c, d \in \{0, 1\}$ โดยบิตในสตริงฐานสอง $s_i$ จะสอดคล้องกับ $(s_{i,4j}, s_{i,4j+1}, s_{i,4j+2}, s_{i,4j+3}) = (a, b, c, d)$
ข้อมูลส่งออก
พิมพ์จำนวนเต็มหนึ่งจำนวน — จำนวนของลำดับ $(p_2, p_3, \dots, p_n)$ ที่ถูกต้อง มอดูโล $998244353$
ตัวอย่าง
5 8 2
95
05
BD
9C
BD
6