連続 3 項の和が k 以下の部分列 Scala編（paizaランク B 相当）

長さ n の数列 a = (a_1, a_2, ..., a_n) が与えられます。

a の部分列 a' は 2^n 個存在しますが、それらのうち、そこから取り出した任意の長さ 3 の連続部分列の要素の和が k 以下になるものの数を求めてください。
つまり、
a'_1 + a'_2 + a'_3 <= k,
a'_2 + a'_3 + a'_4 <= k,
...,
a'_{|a'|-2} + a'_{|a'|-1} + a'_{|a'|} <= k
をすべて満たす部分列 a' の個数を求めてください。
なお、長さ 2 以下 (0 を含む) の部分列については、すべての項の和が k 以下であるような部分列が条件を満たすとします。(空の部分列は常に条件を満たします)

x の部分列 x' は x の要素のうちいくつか (0 個以上) を選んで元の順序を保ったまま並べたものと定義されます。
例えば、(1, 2, 3) の部分列は (), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) の 8 個存在します。

ただし、取り出された部分列が同じでも、その取り出しかたが異なるものは別のものとして数えてください。
また、答えは非常に大きくなる可能性があるため、10^9 で割った余りを出力してください。