CF1185G1 Playlist for Polycarp (easy version)

你现在正在选择歌曲。现在共有 $n$ 首歌，每首歌有一个时长 $t_i$ 和一个编号 $g_i$。 您需要求出有多少种选出若干首歌排成一排的方案，使得任意相邻两首歌的编号不同，且所有歌的时长和恰好为 $T$。

第一行是两个整数 $n, t(1\le n\le15,1\le T\le225)$。 接下来 $n$ 行，每行两个正整数 $t_i , g_i (1\le t_i\le15,1\le g_i\le3)$，表示第 $i$ 首歌曲的时长和编号。

输出一个整数表示方案数。答案对 $10^9 + 7$ 取模。

In the first example, Polycarp can make any of the $ 6 $ possible playlist by rearranging the available songs: $ [1, 2, 3] $ , $ [1, 3, 2] $ , $ [2, 1, 3] $ , $ [2, 3, 1] $ , $ [3, 1, 2] $ and $ [3, 2, 1] $ (indices of the songs are given). In the second example, the first and second songs cannot go in succession (since they have the same genre). Thus, Polycarp can create a playlist in one of $ 2 $ possible ways: $ [1, 3, 2] $ and $ [2, 3, 1] $ (indices of the songs are given). In the third example, Polycarp can make the following playlists: $ [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] $ and $ [4, 3, 2] $ (indices of the songs are given).