22069번 - Числа Фибоначчи 다국어

Числа Фибоначчи являются одной из самых известных и изученных последовательностей чисел. Закономерности на основе этих чисел встречаются в самых неожиданных областях, например, в архитектуре средневековых зданий или живой природе. Ваш знакомый исследователь думает, что нашел новую закономерность, но, чтобы проверить свою гипотезу, ему понадобится ваша помощь.

Напомним, что числа Фибоначчи задаются следующими рекуррентным соотношением: F₁=1, F₂=1, F_i=F_i-1+F_i-2.

Помогите исследователю посчитать сумму k-х степеней первых n чисел Фибоначчи (Σ_{i = 1}ⁿ F_i^k) по модулю 10⁹ + 23.

Первая строка входных данных содержит одно число t (1 ≤ t ≤ 100) —количество тестов. Следующие t строк содержат по одному тесту каждая. Каждый тест задается двумя целыми числами: n, k (1 ≤ n ≤ 10⁹ 1 ≤ k ≤ 10¹⁸) — количество чисел Фибоначчи и степень.

Для каждого набора данных выведите единственное число: сумму k-х степеней первых n чисел Фибоначчи по модулю 10⁹ + 23.