== include(page="template/taskheader" task_id="dsets") ==

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 (x1,y1) şi (x2,y2) este definită ca |x1-x2|+|y1-y2|.

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ă $2$ 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.

Cunoscând valoarea D, determinaţi numărul de mulţimi ce pot fi selectate modulo 1000000007 (109+7).

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 $(x1,y1)$ şi $(x2,y2)$ este definită ca $|x1-x2|+|y1-y2|$.
 
Cunoscând valoarea $D$, determinaţi numărul de mulţimi ce pot fi selectate modulo $1000000007 (10^9^+7)$.

h2. Date de intrare

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

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

h2. 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 1000000007.

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 $1000000007$.

h2. Restricţii

1 <= D <= 1 000 000 000
65% din teste vor avea D <= 100 000

* $1 ≤ D ≤ 1 000 000 000$
* $65%$ din teste vor avea $D ≤ 100 000$

h2. Exemplu

h3. Explicaţie
Pentru primul exemplu cele două mulţimi au următoarea structură:

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

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

== include(page="template/taskfooter" task_id="dsets") ==

9058