محרוזת בינארית $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