Класс матрицы 2×2 и быстрое возведение в степень

Напишите тип-значение Mat2 (матрица 2×2 по модулю 10⁹ + 7) с operator* и функцией возведения в степень. С его помощью отвечайте на запросы: n-е число Фибоначчи по модулю 10⁹ + 7 (F₀ = 0, F₁ = 1).

Ввод: q (1 ≤ q ≤ 1000), затем q чисел n (0 ≤ n ≤ 10¹⁸).

Вывод: q строк с ответами.

Пример 1

Ввод:

5
0
1
2
10
50

Вывод:

0
1
1
55
586268941

Пример 2

Ввод:

2
1000000000000000000
999999999999999999

Вывод:

209783453
470273943