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ă).

Exemplu: 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ța

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 3000017.

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 3000017.

Restricții și precizări

• 1 ≤ c ≤ r ≤ 1000000
• 1 ≤ L ≤ 1000000

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.