Приближается лунный новый год, а Боб получил подарок — рекурсивную последовательность! Последовательность ему очень понравилась, он хочет с ней поиграть.

Пусть $$$f_1, f_2, \ldots, f_i, \ldots$$$ — бесконечная последовательность положительных целых чисел. Боб знает, что, если $$$i > k$$$, то $$$f_i$$$ может быть получена, используя следующую рекуррентную формулу:

$$$$$$f_i = \left(f_{i - 1} ^ {b_1} \cdot f_{i - 2} ^ {b_2} \cdot \cdots \cdot f_{i - k} ^ {b_k}\right) \bmod p,$$$$$$

или, если коротко,

$$$$$$f_i = \left(\prod_{j = 1}^{k} f_{i - j}^{b_j}\right) \bmod p,$$$$$$

где $$$p = 998\,244\,353$$$ (известное простое), $$$b_1, b_2, \ldots, b_k$$$ — известные целочисленные константы, а $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

Боб потерял значения $$$f_1, f_2, \ldots, f_k$$$, что очень печально: ведь они составляют основу последовательности! К счастью, Боб запомнил первые $$$k - 1$$$ элементов последовательности: $$$f_1 = f_2 = \ldots = f_{k - 1} = 1$$$, а также ее $$$n$$$-й элемент: $$$f_n = m$$$. Найдите любое возможное значение $$$f_k$$$. Если решений нет, скажите Бобу, что восстановить его любимую последовательность нельзя.