Fişierul intrare/ieşire:	carry.in, carry.out	Sursă	preOJI 2016, clasele 11-12
Autor	Dan Pracsiu	Adăugată de	Gemene Narcis - Gabriel •narcis_vs
Timp execuţie pe test	0.15 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Carry

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 .

Date de intrare

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.

Date de ieşire

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 .

Restricţii

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ min{100,N}

Exemplu

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

Cum se trimit solutii?