Окно в матрицу - это ее непрерывная подматрица.

Рассмотрим матрицу $2\times n$, в которой каждый элемент равен или 0, или 1.
Пусть $A(k,n)$ будет общим числом такого рода матриц, в которых сумма элементов в каждом окне $2\times k$ равна $k$.

Известно, что $A(3,9) = 560$ и $A(4,20) = 1060870$.

Найдите $A(10^8,10^{16})$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.