| Fişierul intrare/ieşire: | dsets.in, dsets.out | Sursă | Lot Baia Mare 2013 - Baraj 2 Seniori |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Daniel Constantin Anghel •Magnvs |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 (109+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 1000000007.
Restricţii
- 1 ≤ D ≤ 1 000 000 000
- 65% din teste vor avea D ≤ 100 000
Exemplu
| dsets.in | dsets.out |
|---|---|
| 1 | 2 |
| 2 | 21 |
| 3 | 280 |
| 4 | 8400 |
| 12345 | 290642959 |
| 1000000000 | 957938183 |
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
