Zalău01

La herghelia Zalău01 există un grajd pentru cai compus din $N$ boxe numerotate de la $1$ la $N$ și așezate în linie. Momentan câteva dintre boxe sunt ocupate de câte un cal și câteva boxe trebuie păstrate libere din motive de salubritate.

Consiliul hergheliei a decis să mai achiziționeze câțiva cai, dar trebuie să țină cont de niște restricții foarte stricte pentru a nu destabiliza psihologic animalele. Mai exact, pentru un $K$ dat, spunem că doi cai sunt prieteni dacă stau în boxe situate la distanță cel mult $K$. Formal, perechea de cai din boxele $(i, j)$ formează o relație de prietenie dacă $1 \leq i < j \leq N$ și $j - i + 1 \leq K$.

Pentru a asigura o stare emoțională optimă a cailor, trebuie ca în grajd să existe exact $X$ relații de prietenie. Atenție, perechile $(i, j)$ și $(j, i)$ se numără o singura dată.

Cerință

Date fiind $N$, $K$ și $X$ și configurația actuală a grajdului, să se determine numărul de moduri în care herghelia poate achiziționa cai noi astfel încât să respecte restricțiile psihologice. Două moduri sunt diferite dacă există cel puțin o boxă care într-unul dintre ele este ocupată, iar în celălalt nu.

Date de intrare

Pe prima linie, se dau numerele $N$, $K$ și $X$.

Pe a doua linie se află un șir de lungime $N$ format din caracterele $\{`0`, `1`, `?`\}$ unde caracterul 1 reprezintă o boxă deja ocupată de un cal, 0 reprezintă o boxă care trebuie lăsată liberă, iar caracterul ? descrie o boxă pentru care poate sau nu să fie achiziționat un cal.

Date de ieșire

Afișați numărul cerut.

Restricții și precizări

• $2 \leq N \leq 50$
• $2 \leq K \leq N$
• $0 \leq X \leq \frac{N \cdot (N - 1)}{2}$
• Caii țin la intimitatea lor, prin urmare nu pot să stea doi cai în aceeași boxă.

Exemple

stdin

3 2 1
?1?

stdout

2

Explicații

Opțiunile de a achiziționa și așeza caii respectând cerința sunt:
011
110

stdin

4 3 2
1??1

stdout

2

Explicații

Opțiunile de a achiziționa și așeza caii respectând cerința sunt:
1011
1101

stdin

4 3 2
???0

stdout

0

Explicații

Nu există nicio opțiune de a achiziționa cai noi cu configurația actuală a grajdului.