According to Fibonacci sequence, Balu creates a new sequence which is called "Balu sequence".
The definition of Balu sequence is
$
B_i=
\begin{align}
\begin{cases}
1&,\ \text{if }i\leq2\\
(2\ B_{i-1}+3\ B_{i-2})\mod{1000000007}&,\ \text{otherwise}\\
\end{cases}
\end{align}
$
Please help him to find $B_N$ of the sequence.
Only one line contains a positive integer $N\ (N\leq100)$
One line contains an integer that represents $B_N$
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~4 | $N\leq20$ | 9 |
2 | 0~9 | $N\leq30$ | 8 |
3 | 0~15 | No specified restriction | 8 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 |