Candale Silviu (silviu) 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≤100N≤M≤10180≤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