Problem
Oggi Moxxi è di buon umore, quindi vuole diversificare la musica nel suo bar.
Il jukebox memorizza n brani, ognuno dei quali è caratterizzato da due parametri: t
i e g
i, dove t_i — durata del brano in minuti (1 ≤ t
i ≤ 15), g
i — il suo genere (1 ≤ g
i ≤ 3).
Moxxi vuole creare una playlist tale che la sua durata totale sia esattamente T minuti. Il jukebox non interrompe mai le canzoni e le riproduce sempre dall'inizio alla fine. Quindi, se inizia a suonare l'i-esima canzone, ci impiegherà esattamente t
i minuti. A Moxxi inoltre non piace quando due canzoni dello stesso genere vengono riprodotte di seguito o quando le canzoni vengono ripetute.
Aiuta Moxxi a contare il numero di diverse sequenze di brani (il loro ordine è importante), con una durata totale di esattamente T, in modo tale che non contengano due brani consecutivi dello stesso genere e tutti i brani nella playlist siano diversi.
Inserimento:
La prima riga dell'input contiene due numeri interi n e T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — rispettivamente il numero di brani nel jukebox e la durata totale richiesta.
Le n righe successive contengono le descrizioni delle canzoni: la riga i-esima contiene due numeri interi t
i e g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) — rispettivamente la durata dell'i-esimo brano e il suo genere.
Uscita:
Stampa un singolo numero intero — il numero di diverse sequenze di brani, con una durata totale esattamente di T, tale che non contengano due brani consecutivi dello stesso genere e tutti i brani nella playlist siano diversi. Poiché il risultato può essere grande, stampalo modulo 10
9 + 7 (ovvero, il resto quando il numero viene diviso per il numero 10
9 + 7).
Esempi:
| Input |
Uscita |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Spiegazioni:
Nel primo esempio, Moxxi può creare una qualsiasi delle 6 opzioni di playlist riorganizzando i brani disponibili: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] e [3,2,1] (sono indicati i numeri dei brani).
Nel secondo esempio, il primo e il secondo brano non possono essere consecutivi (perché hanno lo stesso genere). Pertanto, Moxxi può creare una playlist in uno dei 2 modi possibili: [1,3,2] e [2,3,1] (sono indicati i numeri dei brani).