Campana per vacche (Gold)

Così come agli esseri umani piace giocare a campana, le vacche di Farmer John hanno ideato la propria versione di questo gioco. Poiché viene praticato da animali goffi che pesano quasi una tonnellata, il gioco della "Campana per vacche" si conclude quasi sempre in un disastro. Tuttavia, sorprendentemente, questo non impedisce alle vacche di giocarci quasi ogni pomeriggio.

Il gioco si svolge su una griglia di dimensioni r \times c, dove ogni cella è contrassegnata da un numero intero compreso nell'intervallo $1\dots k$. Le vacche partono dalla cella nell'angolo in alto a sinistra e devono raggiungere la cella nell'angolo in basso a destra, eseguendo una sequenza di salti. Un salto è valido se e solo se:

1. La cella di destinazione ha un'etichetta diversa da quella della cella corrente.

2. La cella di destinazione si trova almeno una riga più in basso rispetto alla cella corrente.

3. La cella di destinazione si trova almeno una colonna più a destra rispetto alla cella corrente.

Aiuta le vacche a determinare il numero di sequenze distinte di salti validi che permettono di arrivare dalla cella nell'angolo in alto a sinistra alla cella nell'angolo in basso a destra.