Window into a Matrix

 Published on Saturday, 16th January 2021, 10:00 pm; Solved by 408

Problem 743

A window into a matrix is a contiguous sub matrix.

Consider a $2\times n$ matrix where every entry is either 0 or 1.
Let $A(k,n)$ be the total number of these matrices such that the sum of the entries in every $2\times k$ window is $k$.

You are given that $A(3,9) = 560$ and $A(4,20) = 1060870$.

Find $A(10^8,10^{16})$. Give your answer modulo $1\,000\,000\,007$.