Problem
Hoy Moxxi está de buen humor, por eso quiere diversificar la música en su bar.
La máquina de discos almacena n canciones, y cada una de ellas se caracteriza por dos parámetros: t
i y g
i, donde t_i — duración de la canción en minutos (1 ≤ t
i ≤ 15), g
i — su género (1 ≤ g
i ≤ 3).
Moxxi quiere hacer una lista de reproducción tal que su duración total sea exactamente T minutos. La máquina de discos nunca interrumpe las canciones y siempre las reproduce de principio a fin. Por lo tanto, si comienza a reproducir la i-ésima canción, pasará exactamente t
i minutos en ella. A Moxxi tampoco le gusta cuando se reproducen dos canciones del mismo género seguidas o cuando las canciones se repiten.
Ayuda a Moxxi a contar el número de secuencias diferentes de canciones (su orden es importante), con una duración total de exactamente T, de modo que no haya dos canciones consecutivas del mismo género en ellas y todas las canciones de la lista de reproducción sean diferentes.
Entrada:
La primera línea de la entrada contiene dos números enteros n y T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — el número de canciones en el jukebox y la duración total requerida, respectivamente.
Las siguientes n líneas contienen descripciones de las canciones: la i-ésima línea contiene dos números enteros t
i y g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) — la duración de la i-ésima canción y su género, respectivamente.
Salida:
Imprime un solo entero — el número de secuencias diferentes de canciones, con una duración total de exactamente T, de modo que no contengan dos canciones consecutivas del mismo género y todas las canciones de la lista de reproducción sean diferentes. Como la respuesta puede ser grande, imprímela módulo 10
9 + 7 (es decir, el resto cuando el número se divide por el número 10
9 + 7).
Ejemplos:
| Entrada |
Salida |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Explicaciones:
En el primer ejemplo, Moxxi puede crear cualquiera de las 6 opciones de lista de reproducción reorganizando las canciones disponibles: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] y [3,2,1] (se indican los números de las canciones).
En el segundo ejemplo, la primera y la segunda canción no pueden ser consecutivas (porque tienen el mismo género). Por lo tanto, Moxxi puede hacer una lista de reproducción de una de las 2 formas posibles: [1,3,2] y [2,3,1] (se indican los números de las canciones).