Урожай абрикосов Баткена
Агроном из Баткена много лет записывает урожай абрикосов, но по модулю 998244353 (так велит странная традиция его института). Он уверен, что урожай подчиняется линейному рекуррентному закону порядка не больше k: существуют число L ≤ k и коэффициенты c[1], …, c[L], при которых для всех i ≥ L
a[i] = c[1] · a[i−1] + c[2] · a[i−2] + … + c[L] · a[i−L] (mod 998244353).
Коэффициенты агроном потерял, сохранились только первые 2k записей a[0], a[1], …, a[2k−1]. Помогите ему предсказать урожай в году N, то есть найти a[N].
Входные данные
В первой строке — два целых числа k и N (1 ≤ k ≤ 1000, 0 ≤ N ≤ 10¹⁸). Во второй строке — 2k целых чисел a[0], …, a[2k−1] (0 ≤ a[i] < 998244353). Гарантируется, что последовательность действительно подчиняется закону порядка не больше k.
Выходные данные
Выведите a[N] по модулю 998244353.
Пример 1
Вход:
2 10
0 1 1 2
Выход:
55
Пояснение
В первом примере это числа Фибоначчи: a[i] = a[i−1] + a[i−2], a[10] = 55. Во втором — a[i] = 2 · a[i−1] (первые 6 записей 1, 2, 4, 8, 16, 32), a[20] = 2²⁰ = 1048576.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов k ≤ 10 и N ≤ 20000.
Подсказка
Алгоритм Берлекэмпа — Мэсси находит кратчайшую рекурренту по 2L членам последовательности.
Комментарии