Problem
今天莫希西心情不错，所以她想把酒吧里的音乐多样化。
自动点唱机存储 n 首歌曲，每首歌曲由两个参数表征：t
i 和 g
i，其中 t_i —以分钟为单位的歌曲持续时间 (1 ≤ t
i ≤ 15), g
i —它的流派 (1 ≤ g
i ≤ 3).
Moxxi 想要制作一个播放列表，使其总持续时间恰好为 T 分钟。自动点唱机从不打断歌曲，总是从头到尾播放。因此，如果他开始播放第 i 首歌曲，那么他将花费正好 t
i 分钟。莫西也不喜欢同一类型的两首歌曲连续播放或重复播放。
帮助Moxxi统计歌曲不同序列的数量（它们的顺序很重要），总时长恰好为T，使得其中没有连续两首相同类型的歌曲并且播放列表中的所有歌曲都不同。
输入：
输入的第一行包含两个整数 n 和 T (1 ≤ n ≤ 15, 1 ≤ T ≤ 225) —分别是自动点唱机中的歌曲数量和所需的总持续时间。
接下来 n 行包含歌曲的描述：第 i 行包含两个整数 t
i 和 g
i (1 ≤ t
i &le ; 15, 1 ≤g
i ≤ 3) —第 i 首歌曲的持续时间及其流派。
输出：
打印单个整数——不同歌曲序列的数量，总持续时间恰好为 T，因此它们不包含同一流派的两首连续歌曲，并且播放列表中的所有歌曲都是不同的。由于答案可能很大，打印它模 10
9 + 7（即数字除以数字 10
9 + 7 的余数）。
示例：
<正文>
| 输入 |
输出 |
3 3
1 1
1 2
1 3
| 6 |
3 3
1 1
1 1
1 3
| 2 |
说明：
在第一个示例中，Moxxi 可以通过重新排列可用歌曲来创建 6 个播放列表选项中的任何一个：[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1 ]、[ 3,1,2] 和 [3,2,1]（标有歌曲编号）。
在第二个例子中，第一首和第二首歌曲不能连续（因为它们具有相同的流派）。因此，Moxxi 可以通过以下两种可能的方式之一制作播放列表：[1,3,2] 和 [2,3,1]（指示歌曲编号）。