Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-03-20 21:30:47.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:puncte4.in, puncte4.outSursăUrmasii lui Moisil 2015, Clasa a 10-a
AutorVlad StoianAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test1.85 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

Cerinta

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

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.

Date de ieşire

În fişierul puncte4.out se va afla pe prima linie un singur număr reprezentând rezultatul cerut.

Restricţii

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

Exemplu

puncte4.inpuncte4.out
3 4 1
15

Explicaţie

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

puncte4.inpuncte4.out
3 4 2
78
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?