播放列表（困难版）

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

你有 $n$ 首彼此不同的歌曲。第 $i$ 首歌曲的时长为 $t_i$，曲风编号为 $g_i$。

请选择若干首歌曲并排成一个播放列表。每首歌曲至多选择一次，并且播放列表需要同时满足：

• 所选歌曲的总时长恰好为 $T$；
• 任意两首相邻歌曲的曲风编号不同。

求合法播放列表的数量。由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $n,T$。

接下来 $n$ 行，每行包含两个整数 $t_i,g_i$，分别表示第 $i$ 首歌曲的时长和曲风编号。

输出格式

输出一个整数，表示合法播放列表的数量对 $10^9+7$ 取模后的结果。

样例输入 1

3 3
1 1
1 2
1 3

样例输出 1

6

样例输入 2

3 3
1 1
1 1
1 3

样例输出 2

2

样例输入 3

4 10
5 3
2 1
3 2
5 1

样例输出 3

10

数据范围

$1\le n\le 50$，$1\le T\le 2500$，$1\le t_i\le 50$，$1\le g_i\le 3$。

每个测试点独立计分。