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 <= 1018), You should solve for
g(g(g(n))) mod 109 + 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.