Mo şi Fo sunt mari chimişti. Ìn laboratorul lor există şase substanţe chimice, numite mofocarburi, care sunt alcătuite pe baza a trei elemente chimice:
- moxigenul notat cu
M
- fodrogenul notat cu
F
- carboca notat cu
C.
O moleculă de mofocarbură este alcătuită din 2 atomi ai unui element şi un atom al altui element. Se observă că există exact 6 astfel de molecule şi anume:
M2F,
M2C,
F2M,
F2C,
C2M,
C2F.
O reacţie chimică va combina un număr de molecule din cele 6 mofocarburi şi va avea drept rezultat un număr de atomi din fiecare element. Iată două exemple de reacţii corecte:
2M2F + M2C + 3F2M + F2C + 5C2M + C2F => 14M + 11F + 14C
3M2F + 5C2F => 6M + 8F + 10C
Deci în general o reacţie va avea următoarea formă:
x∙F2M + y∙C2M + z∙M2F + u∙C2F + v∙M2C + w∙F2C => m∙M + f∙F + c∙C
unde,
m=x+y+2z+2v,
f=2x+z+u+2w si
c=2y+2u+v+w.
Două reacţii sunt considerate distincte, dacă diferă prin cel puţin un coeficient din primul membru, adică dacă măcar o mofocarbură este folosită de un număr diferit de ori ìn cele două reacţii.
Cerinţă
Cunoscându-se trei numere naturale
m,
f si
c să se calculeze numărul de reacţii distincte care au drept rezultat
m∙M + f∙F + c∙C.
Deoarece acest număr poate fi foarte mare rezultatul va fi afişat modulo
13131.
Date de intrare
Fişierul de intrare
mofocarburi.in conţine pe prima linie cele trei numere naturale
m f c separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire
mofocarburi.out va conţine un singur numar R reprezentând restul împărţirii cu
13131 al numărului de reacţii distincte care dau drept rezultat
m atomi de moxigen,
f atomi de fodorgen si
c atomi de carboca.
Restricţii
• 0 ≤ m, f, c ≤ 100000
• Numărul
m+f+c este pentru toate testele divizibil cu 3.
Exemple
mofocarburi.in | mofocarburi.out | Explicaţii |
2 2 2
| 3
| Avem 3 reacţii cu rezultatul 2M+2F+2C:
M2F + C2F => 2M + 2F + 2C
C2M + F2M => 2M + 2F + 2C
M2C + F2C => 2M + 2F + 2C
|