Bulbuka este o elevă foarte conștiincioasă. În orele de matematică, ea desenează puncte în unele pătrăţele de pe o foaie a caietului, după care le înconjoară cu un dreptunghi de mărime N*M (N≤M) trasat pe liniile imprimate pe foaie. Într-o zi, ea a observat că unele dreptunghiuri pe care le-a trasat au o proprietate specială: toate pătratele de mărime N*N incluse în dreptunghi au același număr de puncte (să-l numim P) desenate în interior.

După oră, profesorul a chemat-o să o întrebe ce desena așa interesant în timpul orei. Bulbuka i-a explicat entuziasmată descoperirea, iar profesorul i-a propus o temă specială: pentru trei valori date N, M și P, să determine câte modalități de a desena punctele există.
Bulbuka a acceptat imediat dar, pentru că nu știe să scrie numere foarte mari, s-a hotărât să prezinte răspunsul modulo 1000000007 (109+7).

Ajunsă acasă, a descoperit că problema e mai grea decât credea inițial și i-ar trebui multe caiete să scrie toate rezolvările posibile. De aceea, vă cere ajutorul.

Cerința

Date fiind N, M și P, să se afișeze rezultatul cerut modulo 1000000007 (109+7).

Date de intrare

Fișierul de intrare puncte2.in conține pe prima linie cele trei numere N, M și P, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire puncte2.out va conține pe prima linie un singur număr reprezentând rezultatul cerut.

Restricții și precizări

• 2≤N≤100
• N≤M≤1018
• 0≤P≤N2
• Pentru 40% din teste N<9

Exemplul 1

puncte2.in

3 4 1

puncte2.out

15

Explicație

Zona gri reprezintă zona conţinută de ambele pătrate de mărime 3x3. Putem plasa punctul ori în zona gri (6 posibilităţi), ori în ambele zone albe (3*3=9 posibilităţi).

Exemplul 1

puncte2.in

3 4 2

puncte2.out

78