User's AC Ratio

92.0% (46/50)

Submission's AC Ratio

38.2% (65/170)

Description

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.

Input Format

Only one line contains a positive integer $N\ (N\leq100)$

Output Format

One line contains an integer that represents $B_N$

Sample Input 1

6

Sample Output 1

121

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N\leq20$ 9
2 0~9 $N\leq30$ 8
3 0~15 No specified restriction 8

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 1 2 3
3 1000 65536 65536 1 2 3
4 1000 65536 65536 1 2 3
5 1000 65536 65536 2 3
6 1000 65536 65536 2 3
7 1000 65536 65536 2 3
8 1000 65536 65536 2 3
9 1000 65536 65536 2 3
10 1000 65536 65536 3
11 1000 65536 65536 3
12 1000 65536 65536 3
13 1000 65536 65536 3
14 1000 65536 65536 3
15 1000 65536 65536 3