## LCC '21 Contest 4 S2 - Artcrime

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

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 units in a cardinal direction — up, down, left, or right. represents hewmatt10's speed, which begins at and accelerates by every time he moves.

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

#### Input Specification

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

#### Output Specification

Output the number of distinct locations hewmatt10 can be at after seconds, modulo .

#### Sample Input 1

1

#### Sample Output 1

4

#### Sample Explanation

hewmatt10 starts at the origin, . 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