36. Пары букв (2.0)

Вам даны строки $s_1, s_2, ..., s_n$ длиной $2$, каждая из которых состоит из заглавных английских символов, и целое число $k$. При этом в этой задаче рассматриваются только первые $20$ символов английского алфавита.

Вам нужно составить из них некоторую строку $w$, при этом вам нужно каждой строке из заданных $n$ поставить в соответствие некоторое требование, обозначаемое числом $c_i$.

Пусть $rev(s)$ $-$ это строка $s$ задом наперед. Если $rev(s) \neq s$, то $i$-е требование означает, что суммарно в строке $w$ строки $s_i$ и $rev(s_i)$ должны встречаться $c_i$ раз как подстрока. Если $rev(s_i) = s_i$, то строка $s_i$ должна входить ровно $c_i$ раз как подстрока. Важно, чтобы строки длины $2$, не указанные в качестве заданных, не встречались в строке. Найдите количество способов поставить в соответствие каждой данной подстроке некоторое требование $1 \le c_i \le k$, чтобы существовала строка $w$, для которой удовлетворены все $n$ требований и не встречаются не указанные строки длины $2$. Так как количество способов может быть большим, выведите его остаток от деления на $998244353$.

В первой строке вам даны числа $1 \le n \le 210$ и $1 \le k \le 10^9$, количество строк длины $2$, для которых нужно определить требование, и ограничение на требования соответственно. В следующей строке вам заданы через пробел сами подстроки длины $2$. Каждая состоит из двух заглавных английских символов, которые в свою очередь являются одними из первых $20$ символов английского алфавита. Гарантируется, что для любой пары $1 \le i < j \le n$ мультимножества символов подстрок $s_i$ и $s_j$ различаются. Для лучшего понимания смотрите примечание.

Выведите искомое количество способов по модулю $998244353$.

Мультимножество $-$ набор элементов(возможно, повторяющихся), в котором порядок не имеет значения.

Два мультимножества различаются, если существует элемент, который встречается разное количество раз в этих мультимножествах.

Суммарное количество различных мультимножеств, содержащих два символа(каждый символ $-$ один из первых $20$ символов английского алфавита), как раз равно $210$.

В первом примере одним из способов будет поставить в соответствие строке $AA$ требование $2$, а строке $AB$ $-$ требование $1$. Тогда подойдет строка $AAAB$.

Во втором примере мы можем всем строкам поставить требование $1$, например. Обратите внимание, строка $ABDCAB$ не может соответствовать корректному набору требований, так как в ней присутствует подстрока $CA$, которая не указана во входных данных.