Given a number sequence with the following formula:
$$A_1=1$$
$$A_2=1$$
$$A_3=1$$
$$...$$
$$A_i=3 \times A_{i-1} - 2 \times A_{i-2} + i^2 - 1$$
Find the $n^{th}$ number.
### Input
- A single line contains an integer $n$.
### Output
- Print the $n^{th}$ number of the sequence modulo $10^9+7$.
### Constraints
- $ 1 \le n \le 10^9$.
### Example
Input:
```
4
```
Output:
```
16
```
