258 : 遅延フィボナッチ数列

数列を以下のように定義する。

• $0 ≤ k ≤ 1999$に対して$g_k = 1$

• $k ≥ 2000$に対して$g_k = g_{k-2000} + g_{k-1999}$

$k = 10^{18}$に対して$g_k \mod 20092010$を求めよ。