emptri

Definim mulțimea punctelor laticiale ordonate ca fiind mulțimea perechilor de puncte din plan $(x,y)$ cu proprietățile: $x$ și $y$ sunt numere naturale și $x \geq y$.

Cerinţă

Considerând un număr natural $N$, să se scrie un program care determină numărul $T$ al triunghiurilor distincte ce îndeplinesc simultan condițiile:

• unul din vârfurile triunghiului este punctul de coordonate $(0,0)$;
• celelalte două vârfuri se gâsesc în două puncte laticiale ordonate cu ambele coordonate $\leq N$;
• în interiorul sau pe marginea triunghiului nu se mai găsesc alte puncte laticiale ordonate.

Exemple

• pentru $N = 2$, există următoarele triunghiuri, deci $T = 3$.
  
• pentru $N = 3$, există următoarele triunghiuri, deci $T = 7$.
  

Date de intrare

Fişierul de intrare emptri.in conţine pe prima linie numărul natural $N$, cu semnificaţia de mai sus.

Date de ieşire

Fişierul de ieşire emptri.out va conţine pe prima linie numărul natural $T$.

Restricţii şi precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• Două puncte laticiale ordonate $(x_1, y_1)$ și $(x_2, y_2)$ sunt distincte dacă $x_1 \neq x_2$ sau $y_1 \neq y_2$;
• Două triunghiuri sunt distincte dacă diferă prin cel puțin un punct laticial asociat vârfurilor.

Exemplul 1

emptri.in

2

emptri.out

3

Explicație

$N = 2$. Există $3$ triunghiuri având un vârf în origine și celelalte două în puncte laticiale ordonate de coordonate $\leq 2$, ce nu mai conțin în interior sau pe margine alte puncte laticiale ordonate.

Exemplul 2

emptri.in

3

emptri.out

7

Explicație

$N = 3$. Există $7$ triunghiuri având un vârf în origine și celelalte două în puncte laticiale ordonate de coordonate $\leq 3$, ce nu mai conțin în interior sau pe margine alte puncte laticiale ordonate.