==Include(page="template/taskheader" task_id="cowfood")==
 
==Include(page="template/raw")==
 
Cowfood
 
Cercetatorii nutritionisti fac experimente asupra amestecului optim de ierburi cu care pot fi hranite vacile. Au adunat K feluri de plante diferite si le-au amestecat, obtinand formule reprezentate prin vectori de forma (a[1], a[2], .. a[K]) unde a[i] reprezinta cantitatea de plante de tipul i folosita in mixtura. Se stie ca pentru orice amestec valid, a[1] + a[2] + ... + a[K] nu depaseste niciodata o valoare data S. Toate experimentele desfasurate au esuat insa, deoarece vacile nu au agreat cantitatile de ierburi din amestecurile testate. Mai mult, cercetatorii si-au dat seama ca pentru orice experiment ratat de forma (a[1], a[2], .. a[K]) , un experiment (b[1], b[2], .. b[K]) cu a[1] <= b[1], a[2] <= b[2], ... a[K] <= b[K] va esua de asemenea.
 
h2. Cerinta
 
Fiindca cercetatorii vor sa termine lucrul cat mai curand posibil, este datoria ta sa afli cate experimente care mai au sanse de a se incheia cu succes au ramas.
 
h2. Date de Intrare
 
Linia 1 a fisierului de intrare contine trei numere naturale K, S si N.
 
Liniile 2 .. N + 1 contin cate K numere (a[1], a[2], .. a[K]) ce reprezinta cate un experiment despre care se stie sigur ca a dat gres.
 
h2. Date de Iesire
 
Fisierul de iesire va contine pe prima linie numarul de amestecuri ramase care mai au inca sanse de a fi agreate de vaci modulo 3210121.
 
h2. Restrictii si precizari
 
* 2 <= K <= 30
* 2 <= S <= 10 000
* 0 <= N <= 20
* orice mixtura valida contine cel putin doua cantitati nenule de ierburi diferite
* toate valorile date in fisierul de intrare se incadreaza in tipuri intregi pe 16 biti
 
h2. Exemplu
 

==Include(page="template/taskheader" task_id="cowfood")==
 
Cercetatorii nutritionisti fac experimente asupra amestecului optim de ierburi cu care pot fi hranite vacile. Au adunat K feluri de plante diferite si le-au amestecat, obtinand formule reprezentate prin vectori de forma ({$a{~1~}, a{~2~}, .. a{~k~}$}) unde a{~i~} reprezinta cantitatea de plante de tipul $i$ folosita in mixtura. Se stie ca pentru orice amestec valid, $a{~1~} + a{~2~} + ... + a{~k~}$ nu depaseste niciodata o valoare data {$S$}. Toate experimentele desfasurate au esuat insa, deoarece vacile nu au agreat cantitatile de ierburi din amestecurile testate. Mai mult, cercetatorii si-au dat seama ca pentru orice experiment ratat de forma ({$a{~1~}, a{~2~}, .. a{~k~}$}) , un experiment ({$b{~1~}, b{~2~}, .. b{~k~}$}) cu $a{~1~} ≤ b{~1~}, a{~2~} ≤ b{~2~}, ... a{~k~} ≤ b{~k~}$ va esua de asemenea.
 
h2. Cerinta
 
Fiindca cercetatorii vor sa termine lucrul cat mai curand posibil, este datoria ta sa afli cate experimente care mai au sanse de a se incheia cu succes au ramas.
 
h2. Date de Intrare
 
Linia $1$ a fisierului de intrare $cowfood.in$ contine trei numere naturale {$K$}, $S$ si {$N$}.
Liniile $2 .. N + 1$ contin cate $K$ numere ({$a{~1~}, a{~2~}, .. a{~k~}$}) ce reprezinta cate un experiment despre care se stie sigur ca a dat gres.
 
h2. Date de Iesire
 
Fisierul de iesire $cowfood.out$ va contine pe prima linie numarul de amestecuri ramase care mai au inca sanse de a fi agreate de vaci modulo {$3210121$}.
 
h2. Restrictii si precizari
 
* $2 ≤ K ≤ 30$
* $2 ≤ S ≤ 10.000$
* $0 ≤ N ≤ 20$
* orice mixtura valida contine cel putin doua cantitati nenule de ierburi diferite
* toate valorile date in fisierul de intrare se incadreaza in tipuri intregi pe $16$ biti
 
h2. Exemplu
 
 
table(example). |_. cowfood.in |_. cowfood.out |
| 2 5 2
1 3
3 1
| 4 |
 
h3. Explicatii
 
Cele 4 amestecuri care mai pot fi incercate sunt $(1, 1), (1, 2), (2, 1), (2, 2)$.
 
 
==Include(page="template/taskfooter" task_id="cowfood")==

| cowfood.in | cowfood.out | Explicatii |
| 2 5 2 | 4 | Cele 4 amestecuri care mai pot fi incercate sunt (1, 1), |
| 1 3 | | (1, 2), (2, 1), (2, 2) |
| 3 1 | | |
| | | |
==Include(page="template/taskfooter" task_id="cowfood")==

796