توجد سلسلة ثنائية $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