Define: $F(0)=0$

$F(1)=1$

$F(n)=F(n-1) + F(n-2) , n>=2$

Define $S(N,K) = \sum_{n=0}^{N} F(1+n*K)$ $mod$ $1000000009$

Given $S(10^{12},100) = 878943097$

Enter the value of $S(221^{221^{10^{18}}},55^{55^{10^{18}}})$