From End to Beginning

Let a(n) be the n-th term of a sequence.
We have the following relation:
a(n) = 3*a(n-1) - 2*a(n-2) + 1*a(n-3)

What is a(1) if we have the following values:
a(10^100 + 0) = 0
a(10^100 + 1) = 1
a(10^100 + 2) = 2

Submit your answer as a(1) Mod 10^9.

Problem maintainer: sinan