dsets

Cerință

Se consideră planul infinit 2D ce conţine toate punctele de coordonate ȋntregi, de pe care s-a şters sistemul de coordonate (astfel nu se mai pot cunoaşte coordonatele unui punct, dar ȋncă se poate calcula distanţa dintre oricare $2$ puncte şi se pot diferenţia sensurile sus-jos şi stânga-dreapta). Iniţial toate punctele de coordonate ȋntregi din plan sunt colorate ȋn alb. Apoi este selectată o mulţime formată din cel puţin $2$ puncte, iar punctele din mulţime sunt colorate ȋn negru astfel încât există următoarea proprietate: există două puncte negre la distanţa Manhattan $D$ iar distanţa Manhatan dintre oricare alte $2$ puncte negre nu depăşeşte $D$. Determinaţi câte mulţimi diferite de puncte cu această proprietate pot fi selectate. Două mulţimi de puncte $A$ şi $B$ se consideră identice dacă conţin acelaşi număr de puncte negre şi dacă există două amplasări posibile ale originii sistemului de coordonate astfel încât punctele din mulţimea $A$ şi cele din mulţimea $B$ să aibă exact aceleaşi coordonate (altfel spus, mulţimea $B$ se poate obţine din mulţimea $A$ prin translaţia pe orizontală şi/sau verticală a tuturor punctelor din $A$). Distanţa Manhattan dintre două puncte $(x_1, y_1)$ şi $(x_2, y_2)$ este definită ca $|x_1 - x_2| + |y_1 - y_2|$.

Cunoscând valoarea $D$, determinaţi numărul de mulţimi ce pot fi selectate modulo $1 \ 000 \ 000 \ 007$ ($10^9+7$).

Date de intrare

Fişierul de intrare dsets.in conţine pe prima linie numărul natural $D$.

Date de ieșire

Fişierul de ieşire dsets.out va conţine pe prima linie un singur număr natural ce reprezintă numărul de mulţimi diferite modulo $1 \ 000 \ 000 \ 007$.

Restricții și precizări

• $1 \leq D \leq 1 \ 000 \ 000 \ 000$
• $65\%$ din teste vor avea $D \leq 100 \ 000$

Exemplul 1

dsets.in

1

dsets.out

2

Explicație

Cele două mulţimi au următoarea structură:

1. două puncte aflate la distanţă $1$ şi având aceeaşi coordonată $x$
2. două puncte aflate la distanţă $1$ şi având aceeaşi coordonată $y$

Exemplul 2

dsets.in

2

dsets.out

21

Exemplul 3

dsets.in

3

dsets.out

280

Exemplul 4

dsets.in

4

dsets.out

8400

Exemplul 5

dsets.in

12345

dsets.out

290642959

Exemplul 6

dsets.in

1000000000

dsets.out

957938183