{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","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 15$$$),$$$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 15, 1 \\le T \\le 225$$$) — 播放器中的歌曲数量和所需的总时长。\u003c/p\u003e\u003cp\u003e接下来的 $$$n$$$ 行包含歌曲的描述:第 $$$i$$$ 行包含两个整数 $$$t_i$$$ 和 $$$g_i$$$ ($$$1 \\le t_i \\le 15, 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"}}]}