hewmatt10 has been caught committing artcrime! Unbeknownst to him while naively constructing his artworks, merely thinking about art has become criminalized and punishable by [REDACTED] as of the A_L_I_C_E_ Act, circa 2035. Luckily for him, there was still time for him to escape before the arrival.

Knowing that [REDACTED] only has access to his current location, hewmatt10 wants to calculate his chance of survival.

Starting as his bunker, hewmatt10 takes a escape route on an infinitely expansive Cartesian plane. He starts at the origin, and with each second, he moves ~S~ units in a cardinal direction — up, down, left, or right. ~S~ represents hewmatt10's speed, which begins at ~1~ and accelerates by ~1~ every time he moves.

After exactly ~K~ seconds, how many distinct final locations can hewmatt10 be at?

Input Specification

The first and only line of input contains a single integer, ~K~.

Output Specification

Output the number of distinct locations hewmatt10 can be at after ~K~ seconds, modulo ~10^9 + 7~.

Subtasks

Subtask 1 [60%]

~(0 \le K \le 20)~

Subtask 2 [40%]

~(0 \le K \le 10^{9})~

Sample Input 1

1

Sample Output 1

4

Sample Explanation

hewmatt10 starts at the origin, ~(0, 0)~. In one step, he could be at ~(0, 1)~, ~(1, 0)~, ~(0, -1)~, or ~(-1, 0)~. Note that staying at a location does not count as a step.

Sample Input 2

2

Sample Output 2

16