CF1185G2 Playlist for Polycarp (hard version)

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

无

无

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).