Parole saturnine

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.