A sequence is defined as:

• $g_k = 1$, for $0 \le k \le 1999$
• $g_k = g_{k-2000} + g_{k - 1999}$, for $k \ge 2000$.

Find $g_k \bmod 20092010$ for $k = 10^{18}$.