Moldovan Robert (use KN) (moldovan_robert_lol) Cerința
Se consideră un cerc. Pe cerc se desemnează N puncte oarecare. Dacă tragem linii între toate perechile de puncte, care este numărul maxim de bucăți în care poate fi descompus cercul? Să se răspundă la Q astfel de scenarii.
Date de intrare
Programul citește de la tastatură numărul Q și pe următoarele Q linii va citi câte un numar N, reprezentând numărul de puncte din scenariul respectiv.
Date de ieșire
Pe următoarele Q linii, programul va afișa răspunsurile pentru fiecare dintre scenarii, modulo 1.000.000.007.
Restricții și precizări
- Se recomandă folosirea fastio
1 ≤ Q ≤ 100.0001 ≤ N ≤ 1.000.000.000- pentru 25% din teste:
Q ≤ 5.000,N ≤ 5.000 - pentru alte 50% din teste:
Q ≤ 100.000,N ≤ 1.000.000 - pentru restul testelor, nicio restricție suplimentară
- deoarece răspunsul poate fi foarte mare, va fi afișat modulo
1.000.000.007.
Exemplu:
Intrare
6 1 2 3 4 5 6
Ieșire
1 2 4 8 16 31
Explicație
Pentru al patrulea scenariu, una dintre posibilele aranjări optime ale celor 4 puncte este următoarea:
