*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, wants to calculate his chance of survival.

Starting as his bunker, units in a cardinal direction — up, down, left, or right. represents 's speed, which begins at and accelerates by every time he moves.

takes a escape route on an infinitely expansive Cartesian plane. He starts at the origin, and with each second, he movesAfter exactly seconds, how many distinct final locations can be at?

#### Input Specification

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

#### Output Specification

Output the number of distinct locations seconds, modulo .

can be at after#### Subtasks

##### Subtask 1 [60%]

##### Subtask 2 [40%]

#### Sample Input 1

`1`

#### Sample Output 1

`4`

#### Sample Explanation

. In one step, he could be at , , , or . Note that staying at a location does **not** count as a step.

#### Sample Input 2

`2`

#### Sample Output 2

`16`

## Comments