Considerăm următorul triunghi:

                        0

                    1      1

                2       2      2

            3      4       4      3

       4       7       8      7       4

   5     11     15     15    11      5

...................................................

Numerotăm liniile triunghiului cu numere naturale începând de la 1. De exemplu, pe linia 1 se află numai numărul 0, pe linia 2 se află 1 1, pe linia 5 se află numerele 4 7 8 7 4.

 

Cerinţa

Deduceţi regula după care este construit triunghiul şi determinaţi suma numerelor pe pe o anumită linie a triunghiului. Pentru că acest număr poate fi foarte mare, se va calcula suma modulo 2011 (restul împărţirii sumei la 2011).

 

Date de intrare

Fişierul de intrare conţine pe prima linie numărul natural n reprezentând numărul liniei de pe care se va calcula suma numerelor.

 

Date de iesire

Fişierul de intrare va conţine un singur număr natural reprezentând suma modulo 2011 a numerelor de pe linia n din triunghi.

 

Restricţii şi precizări:

• 1 <= n <= 10 000 000
• Pentru calculul sumei modulo 2011, se pot utiliza relaţiile:
  • (a + b) mod 2011 = (a mod 2011 + b mod 2011) mod 2011
  • (a * b) mod 2011 = (a mod 2011 * b mod 2011) mod 2011

 

Exemple

Date de intrare	Date de iesire	Explicaţii
5	30	Suma elementelor de pe linia 5 este 4+7+8+7+4 = 30, iar 30 mod 2011 = 30.
Date de intrare	Date de iesire	Explicaţii
13	146	Suma elementelor de pe linia 13 este 8190. 8190 mod 2011 = 146

Nu există indicații de rezolvare