409207: GYM103456 J Dastardly Dalgona

The Front Man needs your help for generating dalgona patterns for the contestants of the upcoming 2022 Crab Games! However, he wants to modify the game to have players walk on top of a field to trace out the designated pattern. Each player is given a field that can be described as a Cartesian plane consisting of all coordinates $$$(x, y)$$$ such that $$$-N \leq x, y \leq N$$$. A player starts facing rightward at $$$(0, 0)$$$ and takes a step $$$1$$$ unit forward. For every subsequent move, they either take a step $$$1$$$ unit forward, or turn $$$90$$$ degrees counterclockwise before taking a step $$$1$$$ unit forward. The player repeats these actions until reaching the point $$$(N, N)$$$ or being disqualified by the overseeing doll. Disqualification occurs if a contestant goes on the same point twice or moves outside the designated area on the plane. An admissible pattern is a sequence of moves that can be traced by the players without being disqualified and ends in the player ceasing to move. Below is an example of such a pattern when $$$N = 2$$$.

There are many possible walks that can be completed by a player, but the Front Man would like to know the maximum number of distinct puzzles he could offer to contestants given $$$N$$$.

The first and only line of input contains a single positive integer $$$N$$$ ($$$1 \leq N \leq 100000$$$) as described above.

Print one number representing the number of possible dalgona patterns the Front Man can create modulo $$$10^9+7$$$.

1

1

2

9

3

82