Come ogni giornalista moderno che si rispetti, Mino deve imparare anche qualche lingua straniera.
Mino, che è un tipo bizzarro, opta per il linguaggio saturnino!
Su Saturno, ogni abitante ha un proprio vocabolario, che è formato dalle parole che non contengono una certa sequenza S di M caratteri consecutivi.
Per pura curiosità, Mino vuole contare quante parole sopravvivono in un tipico vocabolario saturnino.
A tal fine, considera il caso più semplice delle parole su un alfabeto binario, aventi lunghezza prefissata N ≥ M, dove S è composta da Msimboli binari.
Per esempio, se S=01, allora le parole binarie di lunghezza N=4 che non contengono S sono
- 0000, 1000, 1100, 1110, 1111.
Se invece S=11, allora esse sono
- 0000, 1000, 0100, 0010, 1010, 0001, 1001, 0101.
Mino vuole quindi contare le parole binarie di lunghezza N che non contengono S, solo che il loro numero può esplodere al crescere diN.
Allora, indicato con K tale numero, Mino vuole calcolare il valore di K modulo 2011 (in effetti, gira voce che i saturnini sappiano solo contare da 0 fino a 2010 perché tale è il loro numero di dita).
Aiutate Mino a calcolare tale valore.
Dati in Input
Il file input.txt è composto da due righe.
La prima riga contiene due interi positivi M e N separati da uno spazio: M rappresenta la lunghezza della sequenza binaria S da evitare eN la lunghezza delle parole binarie da contare.
La successiva riga contiene M caratteri binari '0' e '1' che rappresentano la sequenza binaria S da evitare.
Dati in Output
Il file output.txt è composto da una sola riga contenente un intero, compreso tra 0 e 2010, che rappresenta il valore K modulo 2011, doveK è il numero di parole binarie di lunghezza N che non contengono S.
Assunzioni
- 1 ≤ N, M ≤ 1000
- Per almeno metà dei casi di prova, su cui saranno valutati i programmi, vale 1 ≤ M ≤ 16.
Esempi
input.txt | output.txt | |
---|---|---|
1 | 2 4 01 |
5 |
2 | 2 4 11 |
8 |
3 | 2 15 11 |
1597 |
4 | 2 16 11 |
563 |
Note
- Ricordiamo che a modulo b = c se e solo se c è il resto della divisione intera tra a e b.
L’operazione di modulo in linguaggio C si effettua con il simbolo di percentuale, in linguaggio Pascal con l’operatore mod. - E’ importante usare sempre il modulo dopo un’operazione aritmetica di conteggio perché i valori intermedi generati possono richiedere più di 32 bit.
Poiché il risultato è K modulo 2011, suggeriamo di sfruttare il fatto che (A + B + C) modulo 2011 = ((A + B) modulo 2011) + C) modulo 2011.
Stessa cosa per le altre operazioni aritmetiche.
In questo modo, i risultati intermedi sono sempre modulo 2011 e possono essere mantenuti in una normale variabile intera a 32 bit.