Cerința
Dându-se n
, un număr natural, să se afle numărul de pătrate care au colţurile coordonate numere întregi cuprinse între 0
şi n
inclusiv.
Date de intrare
Programul citește de la tastatură un număr natural n
.
Date de ieșire
Programul va afişa pe ecran un număr natural, reprezentând numărul de pătrate formate cu cele (n+1)
2
puncte. Deoarece rezultatul poate fi mare, se va afişa răspunsul modulo 666013
.
Restricții și precizări
1 ≤ n ≤ 2.000.000.000
- Pentru teste în valoare de 30 de puncte,
n ≤ 10
- Pentru teste în valoare de 75 de puncte,
n ≤ 2.000.000
Exemplu:
Intrare
2
Ieșire
6
Explicație
Pătratele ce se formează au colţurile:
(0, 0), (0, 1), (1, 1), (1, 0)
(0, 1), (0, 2), (1, 2), (1, 1)
(1, 0), (1, 1), (2, 1), (2, 0)
(1, 1), (1, 2), (2, 2), (2, 1)
(0, 0), (0, 2), (2, 2), (2, 0)
(0, 1), (1, 2), (2, 1), (1, 0)