给定一个长度为 $n$ 的数列 $a_i$ 和 $k$ 个限制形如 $(b_i,c_i)$ 和一个数 $m$ ，求有多少个数列 $x_i$ 满足 $\sum{a_ix_i}\le m$ 且 $x_{b_i}\& 2^{c_i}=0$ 。

$n\le 4*10^4, m\le 10^{18}, k\le 5*10^3, \sum{a_i}\le 4*10^4, b_i\le n, c_i<60, MOD=998244353$

我们发现限制是对于每个 $x_i$ 的二进制位进行的，所以考虑直接将 $a_ix_i$ 分成 $\sum{a_i2^ky_{i,k}}$ ，其中 $y_{i,k}$ 表示 $a_i2^k$ 是否被选择了。这样我们就把问题转化成了 $a_i2^k$ 这共 $60n$ 个物品，其中有 $k$ 个物品被强制不能选择时，选择的物品的总和不超过 $m$ 的方案数。

注意到 $m$ 非常大，所以直接做背包是没有前途的。这时候我们注意到 $a_i2^k$ 这样的一个物品是不会影响到总和的二进制最低的 $k$ 位的，所以我们考虑按照 $2^0$ 到 $2^59$ 这个顺序来对这些物品进行DP。

我们定义 $dp_{i,j,0/1}$ 表示已经选完 $2^i$ 一类的物品，总和 $S$ 满足 $\lfloor \frac{S}{2^{i+1}} \rfloor = j$ ，且 $S\%2^i$ 是否严格大于 $m\%2^i$ 的方案数。