Andrei este pasionat de teoria numerelor. Astăzi el studiază descompunerea numerelor naturale ca sume de alte numere naturale. În studiul său foloseşte şi grafuri. Andrei are un număr natural M pe care încearcă să-l descompună în cât mai multe moduri posibile; pentru aceasta consideră un alt număr natural m1, care va constitui nucleul descompunerii, şi calculează numărul m2=m1 div 2+1; el descompune numărul M ca sumă de mai multe numere egale cu m1, m2 şi respectiv 1 construind un graf conex cu patru tipuri de noduri (noduri de valoare m1, noduri de valoare m2, noduri de valoare 1 şi noduri de valoare 0) şi cu următoarele caracteristici:
suma valorilor asociate tuturor nodurilor este egală cu M;
subgraful obţinut prin eliminarea tuturor nodurilor de valori m2, 1 şi 0 este conex;
fiecare dintre nodurile de valoare m1 are acelaşi grad g, iar nodurile de valori m2, 1 şi 0 au gradul 1 (sunt noduri terminale) şi au legătură (prin singura muchie) doar cu noduri de valoare m1.
Pentru a fi sigur de construcţia tuturor grafurilor cu caracteristicile de mai sus, Andrei procedează în felul următor:
construieşte un graf iniţial care conţine un număr maxim de noduri de valoare m1, după care adaugă (dacă este posibil) un număr maxim de noduri de valoare m2 apoi adaugă noduri de valoare 1 care completează graful astfel încât suma valorilor din toate nodurile să fie egală cu M. În final, dacă mai sunt noduri de valoare m1 care nu au încă gradul g, adaugă alte noduri terminale care vor avea valoarea asociată 0;
pornind de la graful iniţial, şterge unul sau mai multe noduri de valoare m1 şi nodurile de valoare 0 (fără să şteargă noduri de valoare m2 sau de valoare 1) şi adaugă, în schimb, noduri de valoare m2 şi/sau de valoare 1 după una dintre următoarele reguli:
şterge un nod de valoare m1 şi adaugă un nod de valoare m2 şi (m1-m2) noduri de valoare 1;
şterge un nod de valoare m1 şi adaugă m1 noduri de valoare 1;
şterge m2 noduri de valoare m1 şi adaugă m1 noduri de valoare m2
după care completează graful cu muchii şi noduri de valoare 0 astfel încât acest nou graf să respecte caracteristicile descrise mai sus;
la grafurile nou obţinute aplică aceleaşi reguli atât timp cât este posibil;
După ce construieşte toate aceste grafuri le numără doar pe acelea care au cel puţin câte un nod de valori m1, m2 si 1; consideră că două grafuri sunt distincte dacă diferă prin numărul de noduri de valoare m1 şi/sau numărul de noduri de valoare m2 şi/sau numărul de noduri de valoare 1 (nu ia în considerare configuraţia muchiilor şi numărul de noduri de valoare 0).
Cerinţă
Scrieţi un program care să numere cîte grafuri se pot obţine pornind de la graful iniţial, aplicând regulile descrise mai sus (vor fi numărate doar grafurile care au şi noduri de valoare m1, şi noduri de valoare m2, şi noduri de valoare 1).
Date de intrare
Fişierul de intrare nrgraf.in conţine pe prima linie, separate prin spaţiu, numerele naturale M, m1 şi g.
Date de ieşire
Fişierul de ieşire nrgraf.out va conţine pe prima linie numărul de grafuri sau valoarea 0 dacă numărul M nu poate fi descompus folosind valorile m1, m2 şi 1.
Restricţii
20 <= M <= 20 000
3 <= m1 < M
3 <= g <= 10
Exemplu
nrgraf.in
nrgraf.out
Explicaţii
25 8 5
1
Există un singur graf. Graful iniţial este:
din care se obţine, prin aplicarea regulii 1, graful care are şi noduri de valoare 8 şi noduri de valoare 5 şi noduri de valoare 1:
40 5 4
7
Pentru M=40, m1=5, g=4 graful iniţial este 8 x 5 din care se pot obţine 7 grafuri:
(1): 7 x 5 + 1 x 3 + 2 x 1 care este obţinut prin regula 1 din graful iniţial
(2): 6 x 5 + 2 x 3 + 4 x 1 care este obţinut prin regula 1 din graful (1)
(3): 5 x 5 + 3 x 3 + 6 x 1 care este obţinut prin regula 1 din graful (2)
(4): 6 x 5 + 1 x 3 + 7 x 1 care este obţinut prin regula 2 din graful (1)
(5): 5 x 5 + 2 x 3 + 9 x 1 care este obţinut prin regula 2 din graful (2)
(6): 4 x 5 + 5 x 3 + 5 x 1 care este obţinut prin regulile 2 şi 3 din graful iniţial
(7): 4 x 5 + 6 x 3 + 2 x 1 care este obţinut prin regulile 3 şi 1 din graful iniţial.
25 16 6
0
nu se poate descompune numărul 25 folosind numerele 16, 9 şi 1
