← 返回题目列表

Codeforces · 1185/G2

G2. Polycarp 的播放列表(硬版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是限制。

Polycarp 喜欢听音乐,所以他从来没有离开过播放器,即使是在从大学回家的路上。波利卡普在 $$$T$$$ 分钟内克服了从大学到家的距离。

在播放器中,Polycarp 存储 $$$n$$$ 歌曲,每首歌曲都由两个参数来表征:$$$t_i$$$ 和 $$$g_i$$$,其中 $$$t_i$$$ 是歌曲的长度(以分钟为单位)($$$1 \le t_i \le 50$$$),$$$g_i$$$ 是其流派($$$1 \le g_i\le 3$$$)。

Polycarp想要创建这样一个播放列表,以便他可以在从大学到家的路上一直听音乐,而当他到家的时候,播放列表就结束了。坡旅甲从不打断歌曲,总是从头到尾听。因此,如果他开始听第 $$$i$$$ 首歌曲,他将恰好花费 $$$t_i$$$ 分钟来听。波利卡普也不喜欢连续播放两首相同流派的歌曲(即连续/相邻)或重复播放列表中的歌曲。

帮助Polycarpus计算不同序列歌曲的数量(它们的顺序很重要),总持续时间恰好是$$$T$$$,这样其中就没有两首连续的相同流派的歌曲,并且播放列表中的所有歌曲都不同。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$T$$$ ($$$1 \le n \le 50, 1 \le T \le 2500$$$) — 分别是播放器中的歌曲数量和所需的总持续时间。

接下来,$$$n$$$ 行包含歌曲的描述:第 $$$i$$$ 行包含两个整数 $$$t_i$$$ 和 $$$g_i$$$ ($$$1 \le t_i \le 50, 1 \le g_i \le 3$$$) — 分别是第 $$$i$$$ 歌曲的持续时间及其流派。

输出

输出一个整数——不同序列歌曲的数量,总长度恰好为$$$T$$$,使得其中不存在两首连续的同一流派歌曲,并且播放列表中的所有歌曲都不同。由于答案可能很大,因此输出它对 $$$10^9 + 7$$$ 取模(即数量除以 $$$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

注意

在第一个示例中,Polycarp 可以通过重新排列可用歌曲来制作 $$$6$$$ 中的任何一个可能的播放列表:$$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$ 和 $$$[3, 2, 1]$$$ (给出了歌曲的索引)。

在第二个示例中,第一首和第二首歌曲不能连续播放(因为它们具有相同的流派)。因此,Polycarp 可以通过 $$$2$$$ 可能的方式之一创建播放列表:$$$[1, 3, 2]$$$ 和 $$$[2, 3, 1]$$$(给出歌曲的索引)。

在第三个示例中,Polycarp 可以制作以下播放列表:$$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[2, 3, 1]$$$, $$$[3, 1, 2]$$$, $$$[3, 2, 1]$$$、$$$[1, 4]$$$、$$$[4, 1]$$$、$$$[2, 3, 4]$$$ 和 $$$[4, 3, 2]$$$ (给出了歌曲的索引)。