You are given the following recurrent formula:

$T_n = T_{n - 1} + T_{n - 2} + T_{n – 3}$ , at $n > 3$, $T_1 = 3, T_2 = 2, T_3 = 1$

Calculate the following value, $S = (T^2_1 + T^2_2 + ... + T^2_N ) mod (10^9 + 7)$.

Input format

The first line contains one integer $N$.

Output format

Print $S$ denoting the answer to the problem.

Constraints

$1 ⩽ N ⩽ 10^{18}$