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.

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

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

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