Problem
Hoje a Moxxi está bem disposta, por isso quer diversificar a música do seu bar.
A jukebox armazena n músicas, e cada uma delas é caracterizada por dois parâmetros: t
i e g
i, onde t_i — duração da música em minutos (1 ≤ t
i ≤ 15), g
i — seu gênero (1 ≤ g
i ≤ 3).
Moxxi deseja criar uma lista de reprodução de modo que sua duração total seja exatamente T minutos. A jukebox nunca interrompe as músicas e sempre as reproduz do começo ao fim. Assim, se ele começar a tocar a i-ésima música, ele gastará exatamente t
i minutos nela. Moxxi também não gosta quando duas músicas do mesmo gênero são tocadas seguidas ou quando as músicas são repetidas.
Ajude o Moxxi a contar o número de diferentes sequências de músicas (a ordem é importante), com uma duração total de exatamente T, de forma que não haja duas músicas consecutivas do mesmo gênero nelas e todas as músicas da playlist sejam diferentes.
Entrada:
A primeira linha da entrada contém dois inteiros n e T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) — o número de músicas na jukebox e a duração total necessária, respectivamente.
As próximas n linhas contêm descrições das músicas: a i-ésima linha contém dois inteiros t
i e g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) — a duração da i-ésima música e seu gênero, respectivamente.
Saída:
Imprima um único inteiro — o número de sequências diferentes de músicas, com duração total de exatamente T, de modo que não contenham duas músicas consecutivas do mesmo gênero e todas as músicas da playlist sejam diferentes. Como a resposta pode ser grande, imprima-a módulo 10
9 + 7 (ou seja, o resto quando o número é dividido pelo número 10
9 + 7).
Exemplos:
| Entrada |
Saída |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
Explicações:
No primeiro exemplo, o Moxxi pode criar qualquer uma das 6 opções de playlist reorganizando as músicas disponíveis: [1,2,3], [1,3,2], [2,1,3], [2,3,1 ], [ 3,1,2] e [3,2,1] (são indicados os números das músicas).
No segundo exemplo, a primeira e a segunda músicas não podem ser consecutivas (porque são do mesmo gênero). Assim, o Moxxi pode criar uma lista de reprodução de 2 maneiras possíveis: [1,3,2] e [2,3,1] (os números das músicas são indicados).