743 : 行列中の窓

行列中の窓は、途切れのない部分行列である。

全ての要素が0か1である$2 \times n$の行列を考えよう。 全ての$2 \times k$の窓で要素の和（すなわち要素1の個数）が$k$であるような$2 \times n$行列の個数を$A(k, n)$とする。

$A(3, 9) = 560, A(4, 20) = 1060870$である。

$A(108, 1016)$を求め、$1\,000\,000\,007$で割った余りを答えよ。