Problem
Aujourd'hui Moxxi est de bonne humeur, elle souhaite donc diversifier la musique de son bar.
Le juke-box stocke n chansons, et chacune d'elles est caractérisée par deux paramètres : t
i et g
i, où t_i — durée du morceau en minutes (1 ≤ t
i ≤ 15), g
i — son genre (1 ≤ g
i ≤ 3).
Moxxi souhaite créer une liste de lecture telle que sa durée totale soit exactement T minutes. Le jukebox n'interrompt jamais les chansons et les lit toujours du début à la fin. Ainsi, s'il commence à jouer la ième chanson, alors il passera exactement t
i minutes dessus. Moxxi n'aime pas non plus que deux chansons du même genre soient jouées à la suite ou que des chansons soient répétées.
Aidez Moxxi à compter le nombre de séquences différentes de chansons (leur ordre compte), avec une durée totale d'exactement T, de sorte qu'il n'y ait pas deux chansons consécutives du même genre et que toutes les chansons de la playlist soient différentes.
Saisie :
La première ligne de l'entrée contient deux entiers n et T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — le nombre de chansons dans le juke-box et la durée totale requise, respectivement.
Les n lignes suivantes contiennent les descriptions des chansons : la ième ligne contient deux entiers t
i et g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) — la durée de la ième chanson et son genre, respectivement.
Sortie :
Imprimer un seul entier — le nombre de séquences de chansons différentes, d'une durée totale exactement T, telles qu'elles ne contiennent pas deux chansons consécutives du même genre et que toutes les chansons de la playlist sont différentes. Puisque la réponse peut être grande, imprimez-la modulo 10
9 + 7 (c'est-à-dire le reste lorsque le nombre est divisé par le nombre 10
9 + 7).
Exemples :
| Entrée |
Sortie |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Explications :
Dans le premier exemple, Moxxi peut créer n'importe laquelle des 6 options de playlist en réorganisant les chansons disponibles : [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] et [3,2,1] (les numéros de morceau sont indiqués).
Dans le deuxième exemple, les première et deuxième chansons ne peuvent pas être consécutives (car elles ont le même genre). Ainsi, Moxxi peut créer une liste de lecture de l'une des 2 manières possibles : [1,3,2] et [2,3,1] (les numéros des chansons sont indiqués).