Рассмотрим дерево (то есть неориентированный связный граф без циклов) $$$T_1$$$ и дерево $$$T_2$$$. Определим их декартово произведение $$$T_1 \times T_2$$$ следующим образом.

Пусть $$$V$$$ — множество вершин $$$T_1$$$, а $$$U$$$ — множество вершин $$$T_2$$$.

Тогда множеством вершин $$$T_1 \times T_2$$$ является $$$V \times U$$$, то есть множество упорядоченных пар вершин, где первая вершина из $$$V$$$, а вторая из $$$U$$$.

Проведём ребра следующего вида:

• Между $$$(v, u_1)$$$ и $$$(v, u_2)$$$ есть неориентированное ребро, если $$$u_1$$$ и $$$u_2$$$ смежны в графе $$$U$$$.
• Аналогично между $$$(v_1, u)$$$ и $$$(v_2, u)$$$ есть неориентированное ребро, если $$$v_1$$$ и $$$v_2$$$ смежны в графе $$$V$$$.

Обратите внимание на пояснения к примерам, они содержат картинки для произведения деревьев для тестов из примеров.

Рассмотрим граф $$$T_1 \times T_2$$$. Вычислите количество циклов в этом графе (не обязательно простых) длины $$$k$$$. Выведите остаток при делении найденного количества на $$$998244353$$$.

Циклом называется последовательность вершин $$$w_1$$$, $$$w_2$$$, ..., $$$w_k$$$, где $$$w_i \in V \times U$$$, такая что любые две соседние вершины смежны, а также $$$w_1$$$ смежно с $$$w_k$$$. Циклы отличающиеся только циклическим сдвигом или направлением обхода всё равно считаются различными.