从末尾到开头

设 a(n) 为序列的第 n 项。
我们有如下关系：
a(n) = 3*a(n-1) - 2*a(n-2) + 1*a(n-3)

如果我们有以下值，那么 a(1) 是什么：
a(10^100 + 0) = 0
a(10^100 + 1) = 1
a(10^100 + 2) = 2

将您的答案提交为(1) Mod 10^9。

问题维护者： 思南