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