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}mod20092010$ for $k={10}^{18}$.