== include(page="template/taskheader" task_id="carry") ==
Poveste şi cerinţă...
Fie un număr natural nenul X de N cifre. Atunci când efectuăm operaţia de adunare a lui X cu un alt număr Y cifră cu cifră, uneori se obţine transport (carry). De exemplu, dacă X = 156 şi Y = 247, atunci se adună mai întâi 6 şi 7 care dau transport 1, la pasul 2 se adună 5 cu 4 şi cu transportul 1 obţinându-se din nou transportul 1. În total la adunarea 156+247 se obţine de două ori transport 1.
Dându-se numărul X de N cifre şi o valoare K, să se determine câte numere de N cifre dau prin adunarea cu X exact de K ori transport 1. Pentru că acest număr este foarte mare, se va afişa rezultatul modulo $30211$ .
h2. Date de intrare
Fişierul de intrare $carry.in$ ...
Fişierul de intrare $carry.in$ conţine pe prima linie numerele N şi K separate printr-un spaţiu. Pe linia a doua se găsesc, neseparate de spaţii, cele N cifre ale lui X.
h2. Date de ieşire
În fişierul de ieşire $carry.out$ ...
Fişierul de ieşire $carry.out$ va conţine pe prima linie numărul de numere de N cifre care dau de exact K ori transport 1 la adunarea cu X, modulo $30211$ .
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ min{100,N}$
h2. Exemplu
table(example). |_. carry.in |_. carry.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|2 1
98
| 18
|
h3. Explicaţie
...
Numărul X este 98, care are N=2 cifre. Numerele de 2 cifre care adunate cu 98 dau un singur transport egal cu 1 sunt:
10, 11, 20, 21, 30, 31, 40, 41, 50, 51, 60, 61, 70, 71, 80, 81, 90, 91
== include(page="template/taskfooter" task_id="carry") ==
