Wstęp do programowania w C++

Podaj liczbę kwadratów o całkowitych współrzędnych, zawierających się w prostokącie, którego przeciwległe wierzchołki mają współrzędne (0, 0) i (x, x), gdzie liczby x to dodatnia liczba całkowita nie większe niż 10⁶. Wynik podaj modulo 10⁶+7. 

Uwaga! Rozpatrujemy kwadraty, których boki są równoległe lub prostopadłe do osi współrzędnych.

Wejście

W pierwszym wierszu jedna niewielka liczba n określająca liczbę zestawów danych.

Każdy zestaw składa się z jenej liczby x.

Wyjście

Dla każdego zapytania liczba kwadratów modulo 10⁶+7.

Przykład

Wejście:
3
2 
3
10

Wyjście:
5
14
385