tripas

Se consideră aranjamentul piramidal de numere din figură (cunoscut și sub denumirea de triunghiul lui Pascal). În vârful și pe marginile laterale ale piramidei se află numărul $1$. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra. Definim un $tripas(r, c, L)$ ca fiind un triunghi echilateral de numere din interiorul triunghiului lui Pascal, pentru care se precizează poziția $(r,c)$ a vârfului și $L$, lungimea laturii. ($r$ = rând, $c$ = coloană, $L$ = lungime latură).

$tripas(3, 1, 4)$ - reprezintă triunghiul de numere cu vârful poziționat pe rândul al treilea, primul element și care are lungimea laturii de $4$ elemente, adică numerele ($1$), ($1$, $3$), ($1$, $4$, $6$), ($1$, $5$, $10$, $10$) – scrise de sus în jos și de la stânga la dreapta. Pe figura de mai sus, $tripas(3, 1, 4)$ are elementele încadrate în dreptunghiuri.

Notăm cu $S$ suma elementelor unui $tripas(r, c, L)$.

Cerinţă

Să se scrie un program care determină numărul $S$, cunoscând numerele $r$, $c$ și $L$ ce definesc un $tripas(r, c, L)$. Pentru că poate fi foarte mare, se va calcula $S$ modulo $3 \ 000 \ 017$.

Date de intrare

Fişierul de intrare tripas.in conţine pe primul rând numerele naturale $r$, $c$ și $L$ separate prin câte un spațiu.

Date de ieșire

Fişierul de ieşire tripas.out va conţine pe prima linie restul împărțirii numărului $S$ la $3 \ 000 \ 017$.

Restricții și precizări

• $1 \leq c \leq r \leq 10^6$
• $1 \leq L \leq 10^6$

Exemplu

tripas.in

3 1 4

tripas.out

42

Explicație

Triunghiul cu vârful situat pe primul element de pe rândul al treilea și cu lungimea laturii de $4$ elemente, are suma elementelor $1$ + $1$ + $3$ + $1$ + $4$ + $6$ + $1$ + $5$ + $10$ + $10$ = $42$.