Playlist for Polycarp (hard version)

本题显然只需要知道 \(typ=1/2/3\) 的歌的数量分别为什么就可以求出答案了。 先随便求一下 \(f_{i,j,k}\) 表示取 \(i\) 个 \(1\)， \(j\) 个 \(2\), \(k\) 个 \(3\) 的贡献就行了。记得要乘上阶乘。
接下来的问题就转化为一个背包问题。
但是这个背包有 \(3\) 维， 非常不优秀，仔细想想就知道我们不需要知道所有的取法，只需要知道和为 \(T\) 的取法即可。
那我们可以将背包 \(g_{i, j, k}\) 分为一个 \(g_{i,j}\) 和 \(h_{k}\) ，然后最终转移枚举一下就行。

Tips：
背包可以拆分

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
const int mod = 1e9 + 7;
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
    	if(b<0)return x=0,*this;
    	b%=mod-1;
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 55, T = 2510;
modint f[N][N / 2][N / 3][3], g[N / 2][N / 3][T], h[N][T], fac[N];

vector<int> val[3];

int main(){
	//FO("");
	int n, t;
	read(n, t);
	fac[0] = 1;
	U(i, 1, n) {
		int x, g;
		read(x, g);
		fac[i] = fac[i - 1] * i;
		val[g - 1].push_back(x);
	}
	if (val[0].size() < val[1].size()) swap(val[0], val[1]);
	if (val[0].size() < val[2].size()) swap(val[0], val[2]);
	if (val[1].size() < val[2].size()) swap(val[1], val[2]);
	int na = val[0].size(), nb = val[1].size(), nc = val[2].size();
	// cerr << na << " " << nb << ' ' << nc << "\n";
	f[1][0][0][0] = f[0][1][0][1] = f[0][0][1][2] = 1;
	U(a, 0, na) U(b, 0, nb) U(c, 0, nc) {
		int tmp = 0;
		U(d, 0, 2) {
			if (tmp = f[a][b][c][d].x) {
				if (d) f[a + 1][b][c][0] += tmp;
				if (d ^ 1) f[a][b + 1][c][1] += tmp;
				if (d ^ 2) f[a][b][c + 1][2] += tmp;
			}
		}
		f[a][b][c][0] += f[a][b][c][1] + f[a][b][c][2];
		f[a][b][c][0] *= fac[a] * fac[b] * fac[c];
		// cerr << a << " " << b << " " << c << " " << f[a][b][c][0].x << "\n";
	}

	g[0][0][0] = 1;
	int cur = 0;
	for (auto x : val[1]) {
		++cur;
		D(b, cur, 1) D(tm, t, x) g[b][0][tm] += g[b - 1][0][tm - x];
	}
	cur = 0;
	for (auto x : val[2]) {
		++cur;
		U(b, 0, nb) D(c, cur, 1) D(tm, t, x) g[b][c][tm] += g[b][c - 1][tm - x];
	}

	cur = 0;
	h[0][0] = 1;
	for (auto x : val[0]) {
		++cur;
		D(a, cur, 1) D(tm, t, x) h[a][tm] += h[a - 1][tm - x];
	}
	modint ans = 0;
	U(x, 0, t) {
		U(a, 0, na) U(b, 0, nb) U(c, 0, nc)
			ans += h[a][x] * g[b][c][t - x] * f[a][b][c][0];
	}
	writeln(ans.x);
	return 0;
}