1 дискіде ұзындығы $m$ болатын $s_1$ екілік жолы сақталған.
Содан кейін $n - 1$ операция орындалады. $i$-ші операцияда $1 \le p_{i+1} \le i$ болатын диск таңдалып, сол дискідегі $s_{p_{i+1}}$ жолы $i + 1$ дискісіне көшіріледі де, $s_{i+1}$ жолы пайда болады. Алайда көшіру барысында ең көбі $k$ бит аударылып кетуі мүмкін (яғни ең көбі $k$ позицияда қате кетеді).
Сізге әрқайсысының ұзындығы $m$ болатын қорытынды $n$ екілік жолдың барлығы — $s_1, s_2, \dots, s_n$ беріледі. Сіздің міндетіңіз — осы соңғы конфигурацияға әкелуі мүмкін қанша $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$ жолдың әрқайсысында ұзындығы $m/4$ болатын $s'_i$ он алтылық жолы берілген. $s'_i$ жолының әрбір таңбасы — 0–9 немесе A–F таңбаларының бірі, мұндағы $\text{A} = 10, \text{B} = 11, \dots, \text{F} = 15$.
$s'_i$ он алтылық жазылуындағы әрбір цифр $s_i$ екілік жолындағы қатар тұрған төрт битке сәйкес келеді. Нақтырақ айтқанда, әрбір $s'_{i,j}$ цифры үшін $s'_{i,j} = 8a + 4b + 2c + d$ және $a, b, c, d \in \{0, 1\}$ шарттарын қанағаттандыратын жалғыз $(a, b, c, d)$ төрттігі бар екенін дәлелдеуге болады. $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