L. Leveling Diamonds
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After many requests, the UnBalloon Minecraft World Championship has finally been announced! In this championship, there are several different categories, with ostentation being one of them. In this category, the winner will be the one who collects the most diamonds.

Adrielly and Nikolle decided to team up to compete in this category and, to showcase their power, they are willing to collect enough diamonds to build a super tower and activate a beacon up there.

A tower is made up of diamond blocks, where the $$$i$$$-th level consists of $$$(2i + 1)^2$$$ blocks. That is, the first level consists of $$$9$$$ blocks, the second level consists of $$$25$$$ blocks, the third level consists of $$$49$$$ blocks, and so on.

Adrielly and Nikolle are determined to build a tower of height $$$N$$$. At the moment, they are mining and have forgotten to count how many blocks will be needed! Can you help them?

Input

The input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$), the desired height of the tower.

Output

Print, on a single line, the number of blocks needed to build a tower of height $$$N$$$ modulo $$$10^9 + 7$$$.

Examples
Input
1
Output
9
Input
3
Output
83
Input
5
Output
285
Input
3271897334534761
Output
217325831
Note

In the figure below, we have towers with heights $$$4$$$, $$$3$$$, $$$2$$$, and $$$1$$$, respectively.