Fenster in eine Matrix

Problem 743

Ein Fenster in eine Matrix ist eine zusammenhängende Teilmatrix.

Wir betrachten eine 2×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×k-Fenster k ist.

Dann ist A(3,9)=560 und A(4,20)=1060870.

Bestimmen Sie A(108,1016). Geben Sie Ihre Antwort modulo 1\.000\.000\.007.