Find a recurrence 2

Find a recurrence relation for the following sequence:
1, 2, 3, 5, 8, 3, 11, 14, 25, 39, 64, 25, 89, 114, 203, 317, 520, 203, 723, 926,...

Then what is the 10^100-th number modulo 10^9?