{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e简单版本和困难版本之间唯一的区别在于约束条件。\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003ePolycarp 热爱听音乐,所以即使是从大学回家的路上,他也从不离开播放器。Polycarp 恰好需要 $$$T$$$ 分钟的时间从大学到家。\u003c/p\u003e\u003cp\u003e在播放器中,Polycarp 存储了 $$$n$$$ 首歌曲,每首歌曲由两个参数描述: $$$t_i$$$ 和 $$$g_i$$$,其中 $$$t_i$$$ 是歌曲的长度(以分钟为单位), $$$1 \\le t_i \\le 50$$$, $$$g_i$$$ 是歌曲的流派, $$$1 \\le g_i \\le 3$$$。\u003c/p\u003e\u003cp\u003ePolycarp 想要创建一个播放列表,这样他就可以一直在从大学回家的路上听音乐,而在到家的时候,播放列表正好播放完毕。Polycarp 从不中断歌曲,总是从头到尾倾听。因此,如果他开始听第 $$$i$$$ 首歌曲,他将花费 $$$t_i$$$ 分钟完整地倾听。Polycarp 也不喜欢连续播放两首相同流派的歌曲,也不喜欢播放列表中出现重复的歌曲。\u003c/p\u003e\u003cp\u003e帮助 Polycarp 计算不同的歌曲序列数量(顺序重要),总时长恰好为 $$$T$$$ 分钟,使得其中没有两首连续的相同流派歌曲,并且播放列表中的所有歌曲都不相同。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含两个整数 $$$n$$$ 和 $$$T$$$($$$1 \\le n \\le 50, 1 \\le T \\le 2500$$$) — 播放器中的歌曲数量和所需的总时长。\u003c/p\u003e\u003cp\u003e接下来的 $$$n$$$ 行包含歌曲的描述:第 $$$i$$$ 行包含两个整数 $$$t_i$$$ 和 $$$g_i$$$($$$1 \\le t_i \\le 50, 1 \\le g_i \\le 3$$$) — 第 $$$i$$$ 首歌曲的时长和流派。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数 — 不同的歌曲序列数量,总时长恰好为 $$$T$$$ 分钟,使得其中没有两首连续的相同流派歌曲,并且播放列表中的所有歌曲都不相同。由于答案可能很大,输出它对 $$$10^9 + 7$$$ 取模的结果(即除以 $$$10^9 + 7$$$ 的余数)。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 1\n1 2\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 1\n1 1\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 10\n5 3\n2 1\n3 2\n5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,Polycarp 可以通过重新排列可用的歌曲制作出任意 $$$6$$$ 种播放列表: $$$[1, 2, 3]$$$、$$$[1, 3, 2]$$$、$$$[2, 1, 3]$$$、$$$[2, 3, 1]$$$、$$$[3, 1, 2]$$$ 和 $$$[3, 2, 1]$$$(给出了歌曲的索引)。\u003c/p\u003e\u003cp\u003e在第二个示例中,第一首和第二首歌曲不能连续播放(因为它们是相同流派)。因此,Polycarp 可以以 $$$2$$$ 种方式创建播放列表: $$$[1, 3, 2]$$$ 和 $$$[2, 3, 1]$$$(给出了歌曲的索引)。\u003c/p\u003e\u003cp\u003e在第三个示例中,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]$$$(给出了歌曲的索引)。\u003c/p\u003e"}}]}