查询区间中有多少个子集的累加和是 $k$ 的倍数

$n, q \leqslant 10^5$，$a_i \leqslant 10^9$, $k \leqslant 20$

如果要求支持带修的话，可以做吗？（这样应该就用不了猫树了吧QwQ)