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 test3.7 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
  • NM ≤ 1018
  • 0 ≤ PN2
  • 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?