puncte4

Puncte4

== include(page="template/taskheader" task_id="puncte4") ==

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 (10^9^ + 7).

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 (10^9^ + 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.
h2. Cerinta

Date fiind N,M şi P, să se afişeze rezultatul cerut modulo 1000000007 (10^9^ + 7).

Date fiind {**N, M**} şi {**P**}, să se afişeze rezultatul cerut modulo {**1000000007 (10^9^ + 7)**}.

h2. Date de intrare

Pe prima linie a fişierului $puncte4.in$ se află cele trei numere N,M şi P, separate prin câte un spaţiu.

Pe prima linie a fişierului $puncte4.in$ se află cele trei numere {**N, M**} şi {**P**}, separate prin câte un spaţiu.

h2. Date de ieşire

h2. Restricţii

* 2 ≤ N ≤ 100
* N ≤ M ≤ 10^18^
* 0 ≤ P ≤ N^2^
* Pentru 40% din teste N < 9

* 2 ≤ {**N**} ≤ 100
* {**N**} ≤ {**M**} ≤ 10^18^
* 0 ≤ {**P**} ≤ {**N^2^**}
* Pentru {**40%**} din teste {**N**} < 9

h2. Exemplu

|
h3. 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).
{! problema/puncte4?enunt.png 42% !}

{! problema/puncte4?enunt.png 100% !}
 
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).

table(example). |_. puncte4.in |_. puncte4.out |
| 3 4 2