Fenster in eine Matrix
Problem 743
Ein Fenster in eine Matrix ist eine zusammenhängende Teilmatrix.
Wir betrachten eine $2\times n$-Matrix, in der jeder Eintrag entweder 0 oder 1 ist.
Sei $A(k,n)$ die Anzahl aller solcher Matrizen, für die die Summe der Einträge in jedem $2\times k$-Fenster $k$ ist.
Dann ist $A(3,9) = 560$ und $A(4,20) = 1060870$.
Bestimmen Sie $A(10^8,10^{16})$. Geben Sie Ihre Antwort modulo $1\.000\.000\.007$.