A Short problem

　　According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
　　Hence they prefer problems short, too. Here is a short one:
　　Given n (1 <= n <= 10¹⁸), You should solve for
g(g(g(n))) mod 10⁹ + 7
　　where
g(n) = 3g(n - 1) + g(n - 2)
g(1) = 1
g(0) = 0

　　There are several test cases. For each test case there is an integer n in a single line.
　　Please process until EOF (End Of File).

　　For each test case, please print a single line with a integer, the corresponding answer to this case.

0
1
2

0
1
42837

2012 ACM/ICPC Asia Regional Chengdu Online