Приближается лунный новый год, а Боб получил подарок — рекурсивную последовательность! Последовательность ему очень понравилась, он хочет с ней поиграть.
Пусть \(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\). Если решений нет, скажите Бобу, что восстановить его любимую последовательность нельзя.
Выходные данные
Выведите возможное значение \(f_k\), где \(f_k\) — положительное целое число такое, что \(1 \leq f_k < p\). Если есть несколько возможных ответов, выведите любое. Если таких \(f_k\), при которых \(f_n = m\), не существует, выведите \(-1\).
Можно легко показать, что если есть несколько возможных значений \(f_k\), то должно быть хотя бы одно, удовлетворяющее \(1 \leq f_k < p\).
Примечание
В первом примере \(f_4 = f_3^2 \cdot f_2^3 \cdot f_1^5\). Поэтому, если \(f_3 = 4\), то \(f_4 = 16\). Обратите внимание, возможно есть несколько различных ответов.
В третьем примере из \(f_7 = 1\) следует \(f_{23333} = 1\).
В четвертом примере нет такого \(f_1\), что \(f_{88888} = 66666\). Поэтому нужно вывести \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3 5
4 16
|
4
|
|
2
|
5
4 7 1 5 6
7 14187219
|
6
|
|
3
|
8
2 3 5 6 1 7 9 10
23333 1
|
1
|
|
4
|
1
2
88888 66666
|
-1
|
|
5
|
3
998244352 998244352 998244352
4 2
|
-1
|
|
6
|
10
283 463 213 777 346 201 463 283 102 999
2333333 6263423
|
382480067
|