简单版本和困难版本之间的唯一区别是限制。
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]$$$ (给出了歌曲的索引)。