{"extraResources":{"example.01.mu":"TVXzATIgMiAxDQoxDQo=","example.02.mu":"TVXzATMgNCAyDQowMQ0K","example.04.mu":"TVXzATIzIDQyIDMNCjAwMA0K","example.03.mu":"TVXzATcgNSAzDQoxMTANCg=="},"scoring":null,"notes":"Note that a string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deleting zero or more characters from the beginning and zero or more characters from the end.\r\n\r\nIn the first test, all pairs of strings satisfying the conditions are (``\\t{01}'', ``\\t{10}''), (``\\t{01}'', ``\\t{11}''), (``\\t{10}'', ``\\t{01}''), (``\\t{10}'', ``\\t{11}''), (``\\t{11}'', ``\\t{01}''), and (``\\t{11}'', ``\\t{10}'').","legend":"Lisa wrote a program to solve the Longest Common Substring problem. She then used the program to find, for some two strings $s$ and $t$ consisting of characters `\\t{0}' and `\\t{1}', the longest string $w$ that is a substring of both $s$ and $t$. If there were multiple such longest strings, she found an arbitrary one.\r\n\r\nNotably, the length of $w$ Lisa found was very small~--- at most 3.\r\n\r\nLisa remembers $n$ (the length of $s$), $m$ (the length of $t$), and $w$, but she doesn't remember strings $s$ and $t$ themselves. Now she wonders how many pairs of strings $s$ and $t$ exist such that they have lengths $n$ and~$m$, respectively, consist of characters `\\t{0}' and `\\t{1}', and have $w$ as one of their longest common substrings.\r\n\r\nHelp Lisa and find this number of pairs modulo $998\\,244\\,353$. Note that if $n = m$ and $s \\ne t$, pairs $(s, t)$ and $(t, s)$ are considered distinct.","authorLogin":"tourist","language":"english","timeLimit":5000,"output":"Print the number of pairs of strings $(s, t)$ that have $w$ as one of their longest common substrings, modulo $998\\,244\\,353$.","inputFile":"stdin","outputFile":"stdout","input":"The first line contains three integers $n$, $m$, and $k$, denoting the lengths of the strings $s$, $t$, and $w$ ($1 \\le n, m \\le 100$; $1 \\le k \\le \\min(3, n, m)$).\r\n\r\nThe second line contains the string $w$ of length $k$ consisting of characters `\\t{0}' and `\\t{1}'.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"6\r\n","input":"2 2 1\r\n1\r\n","inputFile":"example.01","outputFile":"example.01.a"},{"output":"28\r\n","input":"3 4 2\r\n01\r\n","inputFile":"example.02","outputFile":"example.02.a"},{"output":"399\r\n","input":"7 5 3\r\n110\r\n","inputFile":"example.03","outputFile":"example.03.a"},{"output":"174497840\r\n","input":"23 42 3\r\n000\r\n","inputFile":"example.04","outputFile":"example.04.a"}],"name":"Longest Common Substring","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Андрей Станкевич\\\\\r\n         Разработка: & Геннадий Короткевич\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nДля решения этой задачи нужно придумать, как сжать информацию о каждой строке так, чтобы можно было легко проверить, что некоторая строка $w$ действительно является наибольшей общей подстрокой $s$ и $t$.\r\n\r\nОказывается, такое сжатие несложно выполнить. Рассмотрим все возможные $2^{k+1}$ битовых строк длины $k+1$ и выпишем битовую маску $b(s)$ из $2^{k+1}$ бит, обозначающую, какие из них являются подстроками $s$. Аналогично определим $b(t)$. Тогда, если у $b(s)$ и $b(t)$ есть общие биты, то у $s$ и $t$ есть общая подстрока длины $k+1$, а значит, строка $w$ длины $k$ не может являться их наибольшей общей подстрокой. В противном случае достаточно проверить, что $w$ входит в $s$ и в $t$~--- а это верно, если хотя бы одна из строк $w\\mathtt{0}$, $w\\mathtt{1}$, $\\mathtt{0}w$ или $\\mathtt{1}w$ (длины $k+1$) входит в $b(s)$, и то же с $b(t)$.\r\n\r\nТеперь воспользуемся методом динамического программирования. Пусть $f(n, p, b)$~--- число строк длины $n$, последние $k$ бит которых равны $p$, а маска встреченных подстрок длины $k+1$ равна $b$. Для переходов ``вперёд'' переберём очередной $n+1$-й бит (назовём его $d$), допишем $d$ к строке $p$ справа, добавим подстроку $p$ в маску $b$, и отрежем левый бит от $p$.\r\n\r\nСостояний и переходов у данной функции $O(n \\cdot 2^k \\cdot 2^{2^{k+1}})$, что не слишком много в заданных ограничениях.\r\n\r\nВ последней части решения~--- переборе масок $b(s)$ и $b(t)$~--- можно перебирать только пары масок, не имеющих общих единичных битов. Таких пар ровно $3^{2^{k+1}}$, что тоже не слишком много.\r\n\r\nПриведённый алгоритм работает только в случаях $n > k$ и $m > k$, поэтому случаи $n = k$ или $m = k$ надо рассмотреть отдельно."}