Dsets

dsets

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

Poveste şi cerinţă...

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

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

În fişierul de ieşire $dsets.out$ ...

h2. Restricţii

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. dsets.in |_. dsets.out |

| 1 | 2 |
| 2 | 21 |
| 3 | 280 |
| 4 | 8400 |
| 12345 | 290642959 |
| 1000000000 | 957938183 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

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$

...

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

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

9058